<!DOCTYPE html><html lang="zh-CN" data-theme="light"><head><meta charset="UTF-8"><meta http-equiv="X-UA-Compatible" content="IE=edge"><meta name="viewport" content="width=device-width,initial-scale=1,user-scalable=no"><title>数组的查找 | InsectMk的个人空间</title><meta name="keywords" content="Java,千锋教育,培训"><meta name="author" content="InsectMk,3067836615@qq.com"><meta name="copyright" content="InsectMk"><meta name="format-detection" content="telephone=no"><meta name="theme-color" content="#f7f9fe"><meta name="mobile-web-app-capable" content="yes"><meta name="apple-touch-fullscreen" content="yes"><meta name="apple-mobile-web-app-title" content="数组的查找"><meta name="application-name" content="数组的查找"><meta name="apple-mobile-web-app-capable" content="yes"><meta name="apple-mobile-web-app-status-bar-style" content="#f7f9fe"><meta property="og:type" content="article"><meta property="og:title" content="数组的查找"><meta property="og:url" content="https://insectmk.top/posts/8eef9745/index.html"><meta property="og:site_name" content="InsectMk的个人空间"><meta property="og:description" content="数组的查找线性查找概念 线性查找也叫顺序查找，这是最基本的一种查找方法，从给定的值中进行搜索，从一端开始逐一检查每个元素，直到找到所需元素的过程。 元素序列的排列可以有序，也可以无序。  代码实现1234567891011121314151617181920212223242526272829303"><meta property="og:locale" content="zh-CN"><meta property="og:image" content="https://insectmk.top/static/img/head/insectmk.jpg"><meta property="article:author" content="InsectMk"><meta property="article:tag" content="[&quot;InsectMk&quot;,&quot;个人博客&quot;]"><meta name="twitter:card" content="summary"><meta name="twitter:image" content="https://insectmk.top/static/img/head/insectmk.jpg"><meta name="description" content="数组的查找线性查找概念 线性查找也叫顺序查找，这是最基本的一种查找方法，从给定的值中进行搜索，从一端开始逐一检查每个元素，直到找到所需元素的过程。 元素序列的排列可以有序，也可以无序。  代码实现1234567891011121314151617181920212223242526272829303"><link rel="shortcut icon" href="/static/img/website/favicon.jpg"><link rel="canonical" href="https://insectmk.top/posts/8eef9745/"><link rel="preconnect" href="//cdn.cbd.int"><link rel="preconnect" href="//busuanzi.ibruce.info"><meta name="google-site-verification" content="xxx"><meta name="baidu-site-verification" content="code-xxx"><meta name="msvalidate.01" content="xxx"><link rel="stylesheet" href="/css/index.css"><link rel="stylesheet" href="https://cdn.cbd.int/node-snackbar@0.1.16/dist/snackbar.min.css" media="print" onload='this.media="all"'><link rel="stylesheet" href="https://cdn.cbd.int/@fancyapps/ui@5.0.28/dist/fancybox/fancybox.css" media="print" onload='this.media="all"'><script>let GLOBAL_CONFIG={linkPageTop:{enable:!0,title:"与数百名博主无限进步",addFriendPlaceholder:"昵称（请勿包含博客等字样）：\n网站地址（要求博客地址，请勿提交个人主页）：\n头像图片url（请提供尽可能清晰的图片，我会上传到我自己的图床）：\n描述：\n站点截图（可选）：\n"},peoplecanvas:{enable:!0,img:"https://image.insectmk.cn/hexo-gitee-blog/article/_post/summary/hello-world/cover.jpg"},postHeadAiDescription:void 0,diytitle:void 0,LA51:void 0,greetingBox:void 0,twikooEnvId:"",commentBarrageConfig:void 0,root:"/",preloader:{source:3},friends_vue_info:void 0,navMusic:!0,mainTone:void 0,authorStatus:void 0,algolia:void 0,localSearch:{path:"/search.xml",preload:!0,languages:{hits_empty:"找不到您查询的内容：${query}"}},translate:{defaultEncoding:2,translateDelay:0,msgToTraditionalChinese:"繁",msgToSimplifiedChinese:"简",rightMenuMsgToTraditionalChinese:"转为繁体",rightMenuMsgToSimplifiedChinese:"转为简体"},noticeOutdate:void 0,highlight:{plugin:"highlight.js",highlightCopy:!0,highlightLang:!0,highlightHeightLimit:330},copy:{success:"复制成功",error:"复制错误",noSupport:"浏览器不支持"},relativeDate:{homepage:!1,simplehomepage:!0,post:!1},runtime:"天",date_suffix:{just:"刚刚",min:"分钟前",hour:"小时前",day:"天前",month:"个月前"},copyright:{copy:!0,copyrightEbable:!1,limitCount:50,languages:{author:"作者: InsectMk",link:"链接: ",source:"来源: InsectMk的个人空间",info:"著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。",copySuccess:"复制成功，复制和转载请标注本文地址"}},lightbox:"fancybox",Snackbar:{chs_to_cht:"你已切换为繁体",cht_to_chs:"你已切换为简体",day_to_night:"你已切换为深色模式",night_to_day:"你已切换为浅色模式",bgLight:"#425AEF",bgDark:"#1f1f1f",position:"top-center"},source:{justifiedGallery:{js:"https://cdn.cbd.int/flickr-justified-gallery@2.1.2/dist/fjGallery.min.js",css:"https://cdn.cbd.int/flickr-justified-gallery@2.1.2/dist/fjGallery.css"}},isPhotoFigcaption:!1,islazyload:!1,isAnchor:!1,shortcutKey:void 0,autoDarkmode:!0}</script><script id="config-diff">var GLOBAL_CONFIG_SITE={configTitle:"InsectMk的个人空间",title:"数组的查找",postAI:"",pageFillDescription:"数组的查找, 线性查找, 概念, 代码实现, 二分法查找, 概念, 原理, 代码实现, 优缺点, 插值查找, 概念, 代码实现, 斐波那契查找, 概念, 原理, 代码实现数组的查找线性查找概念线性查找也叫顺序查找这是最基本的一种查找方法从给定的值中进行搜索从一端开始逐一检查每个元素直到找到所需元素的过程元素序列的排列可以有序也可以无序代码实现线性查找指定元素首次出现的下标位置指定元素出现的下标位置的集合顺序查找返回指定元素首次出现的下标位置顺序查找返回指定元素出现的下标位置的集合二分法查找概念二分查找算法也叫折半查找算法当要从一个序列中查找一个元素的时候二分查找是一种非常快速的查找算法二分查找是针对有序数据集合的查找算法如果是无序数据集合就遍历查找二分查找之所以快速是因为它在匹配不成功的时候每次都能排除剩余元素中一半的元素因此可能包含目标元素的有效范围就收缩得很快而不像顺序查找那样每次仅能排除一个元素原理比如有一个有序表数组它是按照从小到大的顺序来进行排列的现在需要在该有序表中查找元素步骤如下首先设置两个指针和分别指向数据集合的第一个数据元素位序为和最后一个数据元素位序为然后把整个数据集合长度分成两半并用一个指针指向它们的临界点所以定义指针指向了中间元素位序也就是说其中和都代表所指向的元素的位序如下图接着将所指向的元素与待查找元素进行比较因为大于说明待查找的元素一定位于和之间所以继续折半则而结果如下图接着又将所指向的元素与待查找元素进行比较由于大于所以继续折半则而结果如下图最后又将所指向的元素与待查找元素进行比较结果相等则查找成功返回指针指向的元素的位序如果查找的元素值不是而是那么在最后一步之前还得继续折半查找最后出现的情况如下图代码实现二分法查找指定元素出现的下标位置指定元素出现的下标位置的集合递归方式指定元素出现的下标位置递归方式指定元素出现的下标位置的集合有序的数组中查找某个元素出现的下标位置不使用递归的二分查找返回出现的下标位置目标在右侧目标在左侧有序的数组中查找某个元素首次出现的下标位置不使用递归的二分查找返回下标集合目标在右侧目标在左侧定义放置索引下标的集合将首次查找的位置放入集合判断是否还有重复值有序的数组中查找某个元素出现的下标位置使用递归的二分查找返回出现的下标位置目标在右侧目标在左侧有序的数组中查找某个元素首次出现的下标位置使用递归的二分查找返回下标集合目标在右侧目标在左侧定义放置索引下标的集合将首次查找的位置放入集合判断是否还有重复值优缺点优点速度快不占空间不开辟新空间缺点必须是有序的数组数据量太小没有意义插值查找概念从折半查找中可以看出折半查找的查找效率还是不错的可是为什么要折半呢为什么不是四分之一八分之一呢打个比方在牛津词典里要查找这个单词会首先翻开字典的中间部分然后继续折半吗肯定不会对于查找单词我们肯定是下意识的往字典的最前部分翻去而查找单词则相反我们会下意识的往字典的最后部分翻去所以在折半查找法的基础上进行改造就出现了插值查找法也叫做按比例查找所以插值查找与折半查找唯一不同的是在于的计算方式上它的计算方式为这样就能快速定位目标数值所在的索引比二分查找可以更快速实现查找自适应获取也就是自适应查找点代码实现插值查找指定元素出现的下标位置指定元素出现的下标位置的集合递归方式指定元素出现的下标位置递归方式指定元素出现的下标位置的集合有序的数组中查找某个元素出现的下标位置不使用递归的二分查找返回出现的下标位置目标在右侧目标在左侧有序的数组中查找某个元素首次出现的下标位置不使用递归的二分查找返回下标集合目标在右侧目标在左侧定义放置索引下标的集合将首次查找的位置放入集合判断是否还有重复值有序的数组中查找某个元素出现的下标位置使用递归的二分查找返回出现的下标位置目标在右侧目标在左侧有序的数组中查找某个元素首次出现的下标位置使用递归的二分查找返回下标集合目标在右侧目标在左侧定义放置索引下标的集合将首次查找的位置放入集合判断是否还有重复值斐波那契查找概念斐波那契查找也叫做黄金分割法查找斐波那契查找也是二分查找的一种提升算法通过运用黄金比例的概念在数列中选择查找点进行查找提高查找效率同样地斐波那契查找也属于一种有序查找算法原理对于斐波那契数列也可以从开始前后两个数字的比值随着数列的增加越来越接近黄金比值比如元素个数为的有序列表在斐波那契数列中是和相加所得把元素个数为的有序列表分成前个数据元素组成的前半段和个数据元素组成的后半段那么前半段元素个数和整个有序表长度的比值接近黄金比值而前后两段长度的比值也接近黄金比值假如要查找的元素在前半段那么继续按照斐波那契数列来看所以继续把前半段分成前个数据元素的前半段和后个元素的后半段继续查找如此反复直到查找成功或失败这样斐波那契数列就被应用到查找算法中了总长度前半段长度后半段长度有序列表的元素个数不是斐波那契数列中的数字时该如何处理呢当有序表的元素个数不是斐波那契数列中的某个数字时需要把有序列表的长度补齐让它成为斐波那契数列中的一个数值如果不是补齐而是将多余的截掉是否可行把原有序列表截断肯定是不可行的因为可能把要查找的目标值截掉每次取斐波那契数列中的某个值时都会进行操作这是因为数组下标从开始代码实现斐波那契的索引下标数组长度的数值在斐波那契数列中对应的索引下标斐波那契的索引下标数组长度的数值在斐波那契数列中对应的索引下标斐波那契的索引下标数组长度的数值在斐波那契数列中对应的索引下标利用工具类构造新数组并指向数组对新构造的数组进行元素补充补充为最高位的数值补充数值的数列左侧有个元素目标值小于所在元素在左侧查找全部元素前部元素后部元素因为左侧有个元素所以可以继续拆分即在的前部继续查找所以即下次循环目标值大于所在元素在右侧查找全部元素前部元素后部元素因为右侧有个元素所以可以继续拆分即在的前部继续查找所以即下次循环定义放置索引下标的集合",isPost:!0,isHome:!1,isHighlightShrink:!1,isToc:!0,postUpdate:"2023-06-26 20:24:46",postMainColor:""}</script><noscript><style type="text/css">#nav{opacity:1}.justified-gallery img{opacity:1}#post-meta time,#recent-posts time{display:inline!important}</style></noscript><script>(e=>{e.saveToLocal={set:(e,t,a)=>{var o;0!==a&&(o=Date.now(),localStorage.setItem(e,JSON.stringify({value:t,expiry:o+864e5*a})))},get:e=>{var t=localStorage.getItem(e);if(t){t=JSON.parse(t);if(!(Date.now()>t.expiry))return t.value;localStorage.removeItem(e)}}},e.getScript=(o,c={})=>new Promise((t,e)=>{let a=document.createElement("script");a.src=o,a.async=!0,a.onerror=e,a.onload=a.onreadystatechange=function(){var e=this.readyState;e&&"loaded"!==e&&"complete"!==e||(a.onload=a.onreadystatechange=null,t())},Object.keys(c).forEach(e=>{a.setAttribute(e,c[e])}),document.head.appendChild(a)}),e.getCSS=(o,c=!1)=>new Promise((t,e)=>{let a=document.createElement("link");a.rel="stylesheet",a.href=o,c&&(a.id=c),a.onerror=e,a.onload=a.onreadystatechange=function(){var e=this.readyState;e&&"loaded"!==e&&"complete"!==e||(a.onload=a.onreadystatechange=null,t())},document.head.appendChild(a)}),e.activateDarkMode=()=>{document.documentElement.setAttribute("data-theme","dark"),null!==document.querySelector('meta[name="theme-color"]')&&document.querySelector('meta[name="theme-color"]').setAttribute("content","#18171d")},e.activateLightMode=()=>{document.documentElement.setAttribute("data-theme","light"),null!==document.querySelector('meta[name="theme-color"]')&&document.querySelector('meta[name="theme-color"]').setAttribute("content","#f7f9fe")};var e=saveToLocal.get("theme"),t=window.matchMedia("(prefers-color-scheme: dark)").matches,a=window.matchMedia("(prefers-color-scheme: light)").matches,o=window.matchMedia("(prefers-color-scheme: no-preference)").matches,c=!t&&!a&&!o,t=(void 0===e?(a?activateLightMode():t?activateDarkMode():(o||c)&&((a=(new Date).getHours())<=6||18<=a?activateDarkMode:activateLightMode)(),window.matchMedia("(prefers-color-scheme: dark)").addListener(e=>{void 0===saveToLocal.get("theme")&&(e.matches?activateDarkMode:activateLightMode)()})):("light"===e?activateLightMode:activateDarkMode)(),saveToLocal.get("aside-status"));void 0!==t&&("hide"===t?document.documentElement.classList.add("hide-aside"):document.documentElement.classList.remove("hide-aside"));/iPad|iPhone|iPod|Macintosh/.test(navigator.userAgent)&&document.documentElement.classList.add("apple")})(window)</script><meta name="generator" content="Hexo 7.3.0"><link rel="alternate" href="/atom.xml" title="InsectMk的个人空间" type="application/atom+xml"><link rel="alternate" href="/rss2.xml" title="InsectMk的个人空间" type="application/rss+xml"></head><body data-type="anzhiyu"><div id="web_bg"></div><div id="an_music_bg"></div><div id="loading-box" onclick="document.getElementById(&quot;loading-box&quot;).classList.add(&quot;loaded&quot;)"><div class="loading-bg"><img class="loading-img nolazyload" alt="加载头像" src="/static/img/head/insectmk.jpg"><div class="loading-image-dot"></div></div></div><script>let preloader={endLoading:()=>{document.getElementById("loading-box").classList.add("loaded")},initLoading:()=>{document.getElementById("loading-box").classList.remove("loaded")}};window.addEventListener("load",()=>{preloader.endLoading()}),setTimeout(function(){preloader.endLoading()},1e4),document.addEventListener("pjax:send",()=>{preloader.initLoading()}),document.addEventListener("pjax:complete",()=>{preloader.endLoading()})</script><link rel="stylesheet" href="https://cdn.cbd.int/anzhiyu-theme-static@1.1.10/progress_bar/progress_bar.css"><script async src="https://cdn.cbd.int/pace-js@1.2.4/pace.min.js" data-pace-options="{ &quot;restartOnRequestAfter&quot;:false,&quot;eventLag&quot;:false}"></script><div class="post" id="body-wrap"><header class="not-top-img" id="page-header"><nav id="nav"><div id="nav-group"><span id="blog_name"><div class="back-home-button"><i class="anzhiyufont anzhiyu-icon-grip-vertical"></i><div class="back-menu-list-groups"><div class="back-menu-list-group"><div class="back-menu-list-title">网页</div><div class="back-menu-list"><a class="back-menu-item" target="_blank" rel="noopener" href="https://insectmk.cn/" title="主博客"><img class="back-menu-item-icon" src="/static/img/website/favicon.jpg" alt="主博客"><span class="back-menu-item-text">主博客</span></a><a class="back-menu-item" href="https://insectmk.top/" title="次博客"><img class="back-menu-item-icon" src="/static/img/website/favicon.jpg" alt="次博客"><span class="back-menu-item-text">次博客</span></a></div></div><div class="back-menu-list-group"><div class="back-menu-list-title">项目</div><div class="back-menu-list"><a class="back-menu-item" target="_blank" rel="noopener" href="https://gitee.com/insectmk/chatbot-web" title="智能聊天机器人网站"><img class="back-menu-item-icon" src="https://image.insectmk.cn/hexo-gitee-blog/project/icon/chatbot-web.jpg" alt="智能聊天机器人网站"><span class="back-menu-item-text">智能聊天机器人网站</span></a></div></div></div></div><a id="site-name" href="/" accesskey="h"><div class="title">InsectMk的个人空间</div><i class="anzhiyufont anzhiyu-icon-house-chimney"></i></a></span><div class="mask-name-container"><div id="name-container"><a id="page-name" href="javascript:anzhiyu.scrollToDest(0, 500)">PAGE_NAME</a></div></div><div id="menus"><div class="menus_items"><div class="menus_item"><a class="site-page faa-parent animated-hover" href="/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-home"></use></svg><span>主页</span></a></div><div class="menus_item"><a class="site-page" href="javascript:void(0);"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-hand-peace"></use></svg><span>娱乐</span></a><ul class="menus_item_child"><li><a class="site-page child faa-parent animated-hover" href="/entertainment/gallery/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-images"></use></svg><span>图库</span></a></li></ul></div><div class="menus_item"><a class="site-page" href="javascript:void(0);"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-comments"></use></svg><span>交流</span></a><ul class="menus_item_child"><li><a class="site-page child faa-parent animated-hover" href="/contact/comments/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-paper-plane"></use></svg><span>留言板</span></a></li><li><a class="site-page child faa-parent animated-hover" href="/contact/link/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-link"></use></svg><span>友链</span></a></li></ul></div><div class="menus_item"><a class="site-page" href="javascript:void(0);"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-compass"></use></svg><span>目录</span></a><ul class="menus_item_child"><li><a class="site-page child faa-parent animated-hover" href="/categories/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-archive"></use></svg><span>分类</span></a></li><li><a class="site-page child faa-parent animated-hover" href="/tags/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-tags"></use></svg><span>标签</span></a></li><li><a class="site-page child faa-parent animated-hover" href="/archives/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-folder-open"></use></svg><span>归档</span></a></li></ul></div><div class="menus_item"><a class="site-page" href="javascript:void(0);"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-server"></use></svg><span>服务</span></a><ul class="menus_item_child"><li><a class="site-page child faa-parent animated-hover" href="/server/left4dead2/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-icons-left__dead_"></use></svg><span>求生之路</span></a></li><li><a class="site-page child faa-parent animated-hover" href="/server/minecraft/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-minecraft"></use></svg><span>我的世界</span></a></li></ul></div><div class="menus_item"><a class="site-page" href="javascript:void(0);"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-clipboard"></use></svg><span>日志</span></a><ul class="menus_item_child"><li><a class="site-page child faa-parent animated-hover" href="/log/website/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-website-with-different-sections"></use></svg><span>个人网站</span></a></li><li><a class="site-page child faa-parent animated-hover" href="/log/pc/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-desktop"></use></svg><span>个人电脑</span></a></li></ul></div><div class="menus_item"><a class="site-page" href="javascript:void(0);"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-bars"></use></svg><span>其他</span></a><ul class="menus_item_child"><li><a class="site-page child faa-parent animated-hover" href="/extend/remind/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-note"></use></svg><span>备忘</span></a></li></ul></div><div class="menus_item"><a class="site-page faa-parent animated-hover" href="/about/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-id-card"></use></svg><span>关于</span></a></div></div></div><div id="nav-right"><div class="nav-button" id="randomPost_button"><a class="site-page" onclick="toRandomPost()" title="随机前往一个文章" href="javascript:void(0);"><i class="anzhiyufont anzhiyu-icon-dice"></i></a></div><div class="nav-button" id="search-button"><a class="site-page social-icon search" href="javascript:void(0);" title="搜索🔍" accesskey="s"><i class="anzhiyufont anzhiyu-icon-magnifying-glass"></i><span> 搜索</span></a></div><input id="center-console" type="checkbox"><label class="widget" for="center-console" title="中控台" onclick="anzhiyu.switchConsole()"><i class="left"></i><i class="widget center"></i><i class="widget right"></i></label><div id="console"><div class="console-card-group-reward"><ul class="reward-all console-card"><li class="reward-item"><a href="/static/img/website/reward/wechat.png" target="_blank"><img class="post-qr-code-img" alt="微信" src="/static/img/website/reward/wechat.png"></a><div class="post-qr-code-desc">微信</div></li><li class="reward-item"><a href="/static/img/website/reward/alipay.png" target="_blank"><img class="post-qr-code-img" alt="支付宝" src="/static/img/website/reward/alipay.png"></a><div class="post-qr-code-desc">支付宝</div></li></ul></div><div class="console-card-group"><div class="console-card-group-left"><div class="console-card" id="card-newest-comments"><div class="card-content"><div class="author-content-item-tips">互动</div><span class="author-content-item-title">最新评论</span></div><div class="aside-list"><span>正在加载中...</span></div></div></div><div class="console-card-group-right"><div class="console-card tags"><div class="card-content"><div class="author-content-item-tips">兴趣点</div><span class="author-content-item-title">寻找你感兴趣的领域</span><div class="card-tags"><div class="item-headline"></div><div class="card-tag-cloud"><a href="/tags/AOP/" style="font-size:1.05rem">AOP<sup>1</sup></a><a href="/tags/Butterfly/" style="font-size:1.05rem">Butterfly<sup>4</sup></a><a href="/tags/Docker/" style="font-size:1.05rem">Docker<sup>6</sup></a><a href="/tags/ElementUI/" style="font-size:1.05rem">ElementUI<sup>1</sup></a><a href="/tags/Frp/" style="font-size:1.05rem">Frp<sup>1</sup></a><a href="/tags/Hexo/" style="font-size:1.05rem">Hexo<sup>8</sup></a><a href="/tags/IntelliJ-IDEA/" style="font-size:1.05rem">IntelliJ IDEA<sup>1</sup></a><a href="/tags/JDK/" style="font-size:1.05rem">JDK<sup>1</sup></a><a href="/tags/JWT/" style="font-size:1.05rem">JWT<sup>1</sup></a><a href="/tags/Java/" style="font-size:1.05rem">Java<sup>35</sup></a><a href="/tags/Junit/" style="font-size:1.05rem">Junit<sup>1</sup></a><a href="/tags/Leanote/" style="font-size:1.05rem">Leanote<sup>1</sup></a><a href="/tags/Maven/" style="font-size:1.05rem">Maven<sup>2</sup></a><a href="/tags/MyBatisPlus/" style="font-size:1.05rem">MyBatisPlus<sup>1</sup></a><a href="/tags/MySQL5-7/" style="font-size:1.05rem">MySQL5.7<sup>1</sup></a><a href="/tags/Mybatis/" style="font-size:1.05rem">Mybatis<sup>1</sup></a><a href="/tags/MybatisPlus/" style="font-size:1.05rem">MybatisPlus<sup>1</sup></a><a href="/tags/OSS/" style="font-size:1.05rem">OSS<sup>1</sup></a><a href="/tags/Spring/" style="font-size:1.05rem">Spring<sup>2</sup></a><a href="/tags/Spring-Boot/" style="font-size:1.05rem">SpringBoot<sup>6</sup></a><a href="/tags/Vue2/" style="font-size:1.05rem">Vue2<sup>9</sup></a><a href="/tags/Vue3/" style="font-size:1.05rem">Vue3<sup>1</sup></a><a href="/tags/Vuetify/" style="font-size:1.05rem">Vuetify<sup>1</sup></a><a href="/tags/Vuex/" style="font-size:1.05rem">Vuex<sup>1</sup></a><a href="/tags/Waline/" style="font-size:1.05rem">Waline<sup>3</sup></a><a href="/tags/mvc/" style="font-size:1.05rem">mvc<sup>3</sup></a><a href="/tags/mybatis/" style="font-size:1.05rem">mybatis<sup>1</sup></a><a href="/tags/profile/" style="font-size:1.05rem">profile<sup>1</sup></a><a href="/tags/spring/" style="font-size:1.05rem">spring<sup>5</sup></a><a href="/tags/springboot/" style="font-size:1.05rem">springboot<sup>4</sup></a><a href="/tags/transaction/" style="font-size:1.05rem">transaction<sup>1</sup></a><a href="/tags/yaml/" style="font-size:1.05rem">yaml<sup>2</sup></a><a href="/tags/%E4%B8%AA%E4%BA%BA%E5%8D%9A%E5%AE%A2/" style="font-size:1.05rem">个人博客<sup>11</sup></a><a href="/tags/%E4%BA%8B%E5%8A%A1/" style="font-size:1.05rem">事务<sup>1</sup></a><a href="/tags/%E5%88%86%E9%A1%B5/" style="font-size:1.05rem">分页<sup>1</sup></a><a href="/tags/%E5%89%8D%E7%AB%AF/" style="font-size:1.05rem">前端<sup>1</sup></a><a href="/tags/%E6%9C%8D%E5%8A%A1%E5%99%A8/" style="font-size:1.05rem">服务器<sup>20</sup></a><a href="/tags/%E6%AF%95%E4%B8%9A%E8%AE%BE%E8%AE%A1/" style="font-size:1.05rem">毕业设计<sup>14</sup></a><a href="/tags/%E7%A6%85%E9%81%93/" style="font-size:1.05rem">禅道<sup>1</sup></a><a href="/tags/%E7%BB%BF%E8%89%B2%E8%A7%A3%E5%8E%8B/" style="font-size:1.05rem">绿色解压<sup>1</sup></a></div></div><hr></div></div><div class="console-card history"><div class="item-headline"><i class="anzhiyufont anzhiyu-icon-box-archiv"></i><span>文章</span></div><div class="card-archives"><div class="item-headline"><i class="anzhiyufont anzhiyu-icon-archive"></i><span>归档</span><a class="card-more-btn" href="/archives/" title="查看更多"> <i class="anzhiyufont anzhiyu-icon-angle-right"></i></a></div><ul class="card-archive-list"><li class="card-archive-list-item"><a class="card-archive-list-link" href="/archives/2024/07/"><span class="card-archive-list-date">七月 2024</span><div class="card-archive-list-count-group"><span class="card-archive-list-count">4</span><span>篇</span></div></a></li><li class="card-archive-list-item"><a class="card-archive-list-link" href="/archives/2024/06/"><span class="card-archive-list-date">六月 2024</span><div class="card-archive-list-count-group"><span class="card-archive-list-count">1</span><span>篇</span></div></a></li><li class="card-archive-list-item"><a class="card-archive-list-link" href="/archives/2024/05/"><span class="card-archive-list-date">五月 2024</span><div class="card-archive-list-count-group"><span class="card-archive-list-count">4</span><span>篇</span></div></a></li><li class="card-archive-list-item"><a class="card-archive-list-link" href="/archives/2024/04/"><span class="card-archive-list-date">四月 2024</span><div class="card-archive-list-count-group"><span class="card-archive-list-count">8</span><span>篇</span></div></a></li><li class="card-archive-list-item"><a class="card-archive-list-link" href="/archives/2024/03/"><span class="card-archive-list-date">三月 2024</span><div class="card-archive-list-count-group"><span class="card-archive-list-count">9</span><span>篇</span></div></a></li><li class="card-archive-list-item"><a class="card-archive-list-link" href="/archives/2024/02/"><span class="card-archive-list-date">二月 2024</span><div class="card-archive-list-count-group"><span class="card-archive-list-count">5</span><span>篇</span></div></a></li><li class="card-archive-list-item"><a class="card-archive-list-link" href="/archives/2024/01/"><span class="card-archive-list-date">一月 2024</span><div class="card-archive-list-count-group"><span class="card-archive-list-count">5</span><span>篇</span></div></a></li><li class="card-archive-list-item"><a class="card-archive-list-link" href="/archives/2023/10/"><span class="card-archive-list-date">十月 2023</span><div class="card-archive-list-count-group"><span class="card-archive-list-count">8</span><span>篇</span></div></a></li></ul></div><hr></div></div></div><div class="button-group"><div class="console-btn-item"><a class="darkmode_switchbutton" title="显示模式切换" href="javascript:void(0);"><i class="anzhiyufont anzhiyu-icon-moon"></i></a></div><div class="console-btn-item" id="consoleHideAside" onclick="anzhiyu.hideAsideBtn()" title="边栏显示控制"><a class="asideSwitch"><i class="anzhiyufont anzhiyu-icon-arrows-left-right"></i></a></div><div class="console-btn-item" id="consoleMusic" onclick="anzhiyu.musicToggle()" title="音乐开关"><a class="music-switch"><i class="anzhiyufont anzhiyu-icon-music"></i></a></div></div><div class="console-mask" onclick="anzhiyu.hideConsole()" href="javascript:void(0);"></div></div><div class="nav-button" id="nav-totop"><a class="totopbtn" href="javascript:void(0);"><i class="anzhiyufont anzhiyu-icon-arrow-up"></i><span id="percent" onclick="anzhiyu.scrollToDest(0,500)">0</span></a></div><div id="toggle-menu"><a class="site-page" href="javascript:void(0);" title="切换"><i class="anzhiyufont anzhiyu-icon-bars"></i></a></div></div></div></nav></header><main id="blog-container"><div class="layout" id="content-inner"><div id="post"><div id="post-info"><div id="post-firstinfo"><div class="meta-firstline"><a class="post-meta-original">原创</a><span class="post-meta-categories"><span class="post-meta-separator"></span><i class="anzhiyufont anzhiyu-icon-inbox post-meta-icon"></i><a class="post-meta-categories" href="/categories/%E6%95%99%E8%82%B2/" itemprop="url">教育</a></span><span class="article-meta tags"><a class="article-meta__tags" href="/tags/Java/" tabindex="-1" itemprop="url"> <span><i class="anzhiyufont anzhiyu-icon-hashtag"></i>Java</span></a><a class="article-meta__tags" href="/tags/%E5%8D%83%E9%94%8B%E6%95%99%E8%82%B2/" tabindex="-1" itemprop="url"> <span><i class="anzhiyufont anzhiyu-icon-hashtag"></i>千锋教育</span></a><a class="article-meta__tags" href="/tags/%E5%9F%B9%E8%AE%AD/" tabindex="-1" itemprop="url"> <span><i class="anzhiyufont anzhiyu-icon-hashtag"></i>培训</span></a></span></div></div><h1 class="post-title" itemprop="name headline">数组的查找</h1><div id="post-meta"><div class="meta-firstline"><span class="post-meta-date"><i class="anzhiyufont anzhiyu-icon-calendar-days post-meta-icon"></i><span class="post-meta-label">发表于</span><time class="post-meta-date-created" itemprop="dateCreated datePublished" datetime="2023-06-26T12:24:46.000Z" title="发表于 2023-06-26 20:24:46">2023-06-26</time><span class="post-meta-separator"></span><i class="anzhiyufont anzhiyu-icon-history post-meta-icon"></i><span class="post-meta-label">更新于</span><time class="post-meta-date-updated" itemprop="dateCreated datePublished" datetime="2023-06-26T12:24:46.000Z" title="更新于 2023-06-26 20:24:46">2023-06-26</time></span></div><div class="meta-secondline"><span class="post-meta-separator"></span><span class="post-meta-wordcount"><i class="anzhiyufont anzhiyu-icon-file-word post-meta-icon" title="文章字数"></i><span class="post-meta-label" title="文章字数">字数总计:</span><span class="word-count" title="文章字数">4k</span><span class="post-meta-separator"></span><i class="anzhiyufont anzhiyu-icon-clock post-meta-icon" title="阅读时长"></i><span class="post-meta-label" title="阅读时长">阅读时长:</span><span>16分钟</span></span><span class="post-meta-separator"></span><span data-flag-title="数组的查找"><i class="anzhiyufont anzhiyu-icon-fw-eye post-meta-icon"></i><span class="post-meta-label" title="阅读量">阅读量:</span><span class="waline-pageview-count" data-path="/posts/8eef9745/" title="访问量"><i class="anzhiyufont anzhiyu-icon-spinner anzhiyu-spin"></i></span></span><span class="post-meta-separator"> </span><span class="post-meta-position" title="作者IP属地为成都"><i class="anzhiyufont anzhiyu-icon-location-dot"></i>成都</span><span class="post-meta-separator"></span><span class="post-meta-commentcount"><i class="anzhiyufont anzhiyu-icon-comments post-meta-icon"></i><span class="post-meta-label">评论数:</span><a href="/posts/8eef9745/#post-comment"><span class="waline-comment-count" data-path="/posts/8eef9745/"><i class="anzhiyufont anzhiyu-icon-spinner anzhiyu-spin"></i></span></a></span></div></div></div><article class="post-content" id="article-container" itemscope itemtype="https://insectmk.top/posts/8eef9745/"><header><a class="post-meta-categories" href="/categories/%E6%95%99%E8%82%B2/" itemprop="url">教育</a><a href="/tags/Java/" tabindex="-1" itemprop="url">Java</a><a href="/tags/%E5%8D%83%E9%94%8B%E6%95%99%E8%82%B2/" tabindex="-1" itemprop="url">千锋教育</a><a href="/tags/%E5%9F%B9%E8%AE%AD/" tabindex="-1" itemprop="url">培训</a><h1 id="CrawlerTitle" itemprop="name headline">数组的查找</h1><span itemprop="author" itemscope itemtype="http://schema.org/Person">InsectMk</span><time itemprop="dateCreated datePublished" datetime="2023-06-26T12:24:46.000Z" title="发表于 2023-06-26 20:24:46">2023-06-26</time><time itemprop="dateCreated datePublished" datetime="2023-06-26T12:24:46.000Z" title="更新于 2023-06-26 20:24:46">2023-06-26</time></header><h1 id="数组的查找"><a href="#数组的查找" class="headerlink" title="数组的查找"></a>数组的查找</h1><h2 id="线性查找"><a href="#线性查找" class="headerlink" title="线性查找"></a>线性查找</h2><h3 id="概念"><a href="#概念" class="headerlink" title="概念"></a>概念</h3><blockquote><p>线性查找也叫顺序查找，这是最基本的一种查找方法，从给定的值中进行搜索，从一端开始逐一检查每个元素，直到找到所需元素的过程。</p><p>元素序列的排列可以有序，也可以无序。</p></blockquote><h3 id="代码实现"><a href="#代码实现" class="headerlink" title="代码实现"></a>代码实现</h3><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">Test01</span> &#123;</span><br><span class="line">	<span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">main</span><span class="params">(String[] args)</span> &#123;</span><br><span class="line">		<span class="comment">//线性查找</span></span><br><span class="line">		</span><br><span class="line">		<span class="type">int</span>[] arr = &#123;<span class="number">45</span>, <span class="number">62</span>, <span class="number">15</span>,<span class="number">62</span>, <span class="number">78</span>, <span class="number">30</span>&#125;;</span><br><span class="line">		</span><br><span class="line">		<span class="type">int</span> <span class="variable">index</span> <span class="operator">=</span> sequentialSearch01(arr, <span class="number">62</span>);</span><br><span class="line">		System.out.println(<span class="string">&quot;指定元素首次出现的下标位置：&quot;</span> + index);</span><br><span class="line">		</span><br><span class="line">		List&lt;Integer&gt; indexList = sequentialSearch02(arr, <span class="number">62</span>);</span><br><span class="line">		System.out.println(<span class="string">&quot;指定元素出现的下标位置的集合：&quot;</span> + Arrays.toString(indexList.toArray()));</span><br><span class="line">	&#125;</span><br><span class="line">	</span><br><span class="line">	<span class="comment">/**</span></span><br><span class="line"><span class="comment">	 * 顺序查找</span></span><br><span class="line"><span class="comment">	 * 返回指定元素首次出现的下标位置</span></span><br><span class="line"><span class="comment">	 */</span></span><br><span class="line">	<span class="keyword">public</span> <span class="keyword">static</span> <span class="type">int</span> <span class="title function_">sequentialSearch01</span><span class="params">(<span class="type">int</span>[] arr,<span class="type">int</span> value)</span>&#123;</span><br><span class="line">		<span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span>; i &lt; arr.length; i++) &#123;</span><br><span class="line">			<span class="keyword">if</span>(arr[i] == value)&#123;</span><br><span class="line">				<span class="keyword">return</span> i;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">return</span> -<span class="number">1</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	</span><br><span class="line">	<span class="comment">/**</span></span><br><span class="line"><span class="comment">	 * 顺序查找</span></span><br><span class="line"><span class="comment">	 * 返回指定元素出现的下标位置的集合</span></span><br><span class="line"><span class="comment">	 */</span></span><br><span class="line">	<span class="keyword">public</span> <span class="keyword">static</span> List&lt;Integer&gt; <span class="title function_">sequentialSearch02</span><span class="params">(<span class="type">int</span>[] arr,<span class="type">int</span> value)</span>&#123;</span><br><span class="line">		List&lt;Integer&gt; list = <span class="keyword">new</span> <span class="title class_">ArrayList</span>&lt;&gt;();</span><br><span class="line">		<span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span>; i &lt; arr.length; i++) &#123;</span><br><span class="line">			<span class="keyword">if</span>(arr[i] == value)&#123;</span><br><span class="line">				list.adds(i);</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">return</span> list;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h2 id="二分法查找"><a href="#二分法查找" class="headerlink" title="二分法查找"></a>二分法查找</h2><h3 id="概念-1"><a href="#概念-1" class="headerlink" title="概念"></a>概念</h3><blockquote><p>二分查找(Binary Search)算法，也叫折半查找算法。</p><p>当要从一个序列中查找一个元素的时候，二分查找是一种非常快速的查找算法。</p><p>二分查找是针对有序数据集合的查找算法，如果是无序数据集合就遍历查找。</p><p>二分查找之所以快速，是因为它在匹配不成功的时候，每次都能排除剩余元素中一半的元素。因此可能包含目标元素的有效范围就收缩得很快，而不像顺序查找那样，每次仅能排除一个元素。</p></blockquote><h3 id="原理"><a href="#原理" class="headerlink" title="原理"></a>原理</h3><blockquote><p>比如有一个有序表数组[1,3,5,7,9,11,13,15,17,19,21]，它是按照从小到大的顺序来进行排列的，现在需要在该有序表中查找元素19，步骤如下：</p><ol><li><p>首先设置两个指针low和high，分别指向数据集合的第一个数据元素1(位序为0)和最后一个数据元素21(位序为10)。</p><p>然后把整个数据集合长度分成两半，并用一个指针指向它们的临界点，所以定义指针mid指向了中间元素11(位序5)，也就是说mid&#x3D;(high+low)&#x2F;2，其中high和low都代表所指向的元素的位序，如下图：</p></li></ol></blockquote><img src="https://image.insectmk.cn/hexo-gitee-blog/article/_post/education/qianfeng/day09-2/image-20220808214656128.png" alt="image-20220808214656128" style="zoom:67%"><blockquote><ol start="2"><li><p>接着，将mid所指向的元素(11)与待查找元素(19)进行比较。</p><p>因为19大于11，说明待查找的元素(19)一定位于mid和high之间。所以继续折半，则low &#x3D; mid+1，而mid &#x3D; (low+high)&#x2F;2，结果如下图：</p></li></ol></blockquote><img src="https://image.insectmk.cn/hexo-gitee-blog/article/_post/education/qianfeng/day09-2/image-20220808214725572.png" alt="image-20220808214725572" style="zoom:67%"><blockquote><ol start="3"><li>接着，又将mid所指向的元素(17)与待查找元素(19)进行比较，由于19大于17，所以继续折半，则low &#x3D; mid+1，而mid &#x3D; (low+high)&#x2F;2，结果如下图：</li></ol></blockquote><img src="https://image.insectmk.cn/hexo-gitee-blog/article/_post/education/qianfeng/day09-2/image-20220808214745964.png" alt="image-20220808214745964" style="zoom:67%"><blockquote><ol start="4"><li><p>最后，又将mid所指向的元素(19)与待查找元素(19)进行比较，结果相等，则查找成功，返回mid指针指向的元素的位序。</p><p>如果查找的元素值不是19，而是20，那么在最后一步之前还得继续折半查找，最后出现的情况如下图：</p></li></ol></blockquote><img src="https://image.insectmk.cn/hexo-gitee-blog/article/_post/education/qianfeng/day09-2/image-20220808214813238.png" alt="image-20220808214813238" style="zoom:67%"><h3 id="代码实现-1"><a href="#代码实现-1" class="headerlink" title="代码实现"></a>代码实现</h3><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br><span class="line">128</span><br><span class="line">129</span><br><span class="line">130</span><br><span class="line">131</span><br><span class="line">132</span><br><span class="line">133</span><br><span class="line">134</span><br><span class="line">135</span><br><span class="line">136</span><br><span class="line">137</span><br><span class="line">138</span><br><span class="line">139</span><br><span class="line">140</span><br><span class="line">141</span><br><span class="line">142</span><br><span class="line">143</span><br><span class="line">144</span><br><span class="line">145</span><br><span class="line">146</span><br><span class="line">147</span><br><span class="line">148</span><br><span class="line">149</span><br><span class="line">150</span><br><span class="line">151</span><br><span class="line">152</span><br><span class="line">153</span><br><span class="line">154</span><br><span class="line">155</span><br><span class="line">156</span><br><span class="line">157</span><br><span class="line">158</span><br><span class="line">159</span><br><span class="line">160</span><br><span class="line">161</span><br><span class="line">162</span><br><span class="line">163</span><br><span class="line">164</span><br><span class="line">165</span><br><span class="line">166</span><br><span class="line">167</span><br><span class="line">168</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">Test01</span> &#123;</span><br><span class="line">	<span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">main</span><span class="params">(String[] args)</span> &#123;</span><br><span class="line">		<span class="comment">//二分法查找</span></span><br><span class="line"></span><br><span class="line">		<span class="type">int</span>[] arr = &#123;<span class="number">1</span>,<span class="number">2</span>,<span class="number">3</span>,<span class="number">4</span>,<span class="number">5</span>,<span class="number">6</span>,<span class="number">7</span>,<span class="number">8</span>,<span class="number">9</span>,<span class="number">11</span>,<span class="number">11</span>,<span class="number">11</span>,<span class="number">11</span>,<span class="number">11</span>,<span class="number">11</span>&#125;;</span><br><span class="line"></span><br><span class="line">		<span class="type">int</span> <span class="variable">index</span> <span class="operator">=</span> binarySearch01(arr, <span class="number">11</span>);</span><br><span class="line">		System.out.println(<span class="string">&quot;指定元素出现的下标位置：&quot;</span> + index);</span><br><span class="line"></span><br><span class="line">		List&lt;Integer&gt; indexList = binarySearch02(arr, <span class="number">11</span>);</span><br><span class="line">		System.out.println(<span class="string">&quot;指定元素出现的下标位置的集合：&quot;</span> + Arrays.toString(indexList.toArray()));</span><br><span class="line"></span><br><span class="line">		index = recursionbinarySearch01(arr, <span class="number">0</span>, arr.length-<span class="number">1</span>, <span class="number">11</span>);</span><br><span class="line">		System.out.println(<span class="string">&quot;递归方式 - 指定元素出现的下标位置：&quot;</span> + index);</span><br><span class="line"></span><br><span class="line">		indexList = recursionbinarySearch02(arr, <span class="number">0</span>, arr.length-<span class="number">1</span>, <span class="number">11</span>);</span><br><span class="line">		System.out.println(<span class="string">&quot;递归方式 - 指定元素出现的下标位置的集合：&quot;</span> + Arrays.toString(indexList.toArray()));</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="comment">/**</span></span><br><span class="line"><span class="comment">	 * 有序的数组中查找某个元素出现的下标位置</span></span><br><span class="line"><span class="comment">	 * 不使用递归的二分查找</span></span><br><span class="line"><span class="comment">	 * 返回出现的下标位置</span></span><br><span class="line"><span class="comment">	 */</span></span><br><span class="line">	<span class="keyword">public</span> <span class="keyword">static</span> <span class="type">int</span> <span class="title function_">binarySearch01</span><span class="params">(<span class="type">int</span>[] arr,<span class="type">int</span> val)</span>&#123;</span><br><span class="line"></span><br><span class="line">		<span class="type">int</span> <span class="variable">low</span> <span class="operator">=</span> <span class="number">0</span>;</span><br><span class="line">		<span class="type">int</span> <span class="variable">high</span> <span class="operator">=</span> arr.length-<span class="number">1</span>;</span><br><span class="line"></span><br><span class="line">		<span class="keyword">while</span>(low &lt;= high)&#123;</span><br><span class="line">			<span class="type">int</span> <span class="variable">mid</span> <span class="operator">=</span> (low + high)/<span class="number">2</span>;</span><br><span class="line"></span><br><span class="line">			<span class="keyword">if</span>(val &gt; arr[mid])&#123;</span><br><span class="line">				<span class="comment">//目标在右侧</span></span><br><span class="line">				low = mid+<span class="number">1</span>;</span><br><span class="line">			&#125;<span class="keyword">else</span> <span class="keyword">if</span>(val &lt; arr[mid])&#123;</span><br><span class="line">				<span class="comment">//目标在左侧</span></span><br><span class="line">				high = mid-<span class="number">1</span>;</span><br><span class="line">			&#125;<span class="keyword">else</span>&#123;</span><br><span class="line">				<span class="keyword">return</span> mid;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">return</span> -<span class="number">1</span>;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="comment">/**</span></span><br><span class="line"><span class="comment">	 * 有序的数组中查找某个元素首次出现的下标位置</span></span><br><span class="line"><span class="comment">	 * 不使用递归的二分查找</span></span><br><span class="line"><span class="comment">	 * 返回下标集合</span></span><br><span class="line"><span class="comment">	 */</span></span><br><span class="line">	<span class="keyword">public</span> <span class="keyword">static</span> List&lt;Integer&gt; <span class="title function_">binarySearch02</span><span class="params">(<span class="type">int</span>[] arr,<span class="type">int</span> val)</span>&#123;</span><br><span class="line"></span><br><span class="line">		<span class="type">int</span> <span class="variable">low</span> <span class="operator">=</span> <span class="number">0</span>;</span><br><span class="line">		<span class="type">int</span> <span class="variable">high</span> <span class="operator">=</span> arr.length-<span class="number">1</span>;</span><br><span class="line"></span><br><span class="line">		<span class="keyword">while</span>(low &lt;= high)&#123;</span><br><span class="line">			<span class="type">int</span> <span class="variable">mid</span> <span class="operator">=</span> (low + high)/<span class="number">2</span>;</span><br><span class="line"></span><br><span class="line">			<span class="keyword">if</span>(val &gt; arr[mid])&#123;</span><br><span class="line">				<span class="comment">//目标在右侧</span></span><br><span class="line">				low = mid+<span class="number">1</span>;</span><br><span class="line">			&#125;<span class="keyword">else</span> <span class="keyword">if</span>(val &lt; arr[mid])&#123;</span><br><span class="line">				<span class="comment">//目标在左侧</span></span><br><span class="line">				high = mid-<span class="number">1</span>;</span><br><span class="line">			&#125;<span class="keyword">else</span>&#123;</span><br><span class="line">				<span class="comment">// 定义放置索引下标的集合</span></span><br><span class="line">				List&lt;Integer&gt; list = <span class="keyword">new</span> <span class="title class_">ArrayList</span>&lt;&gt;();</span><br><span class="line">				<span class="comment">// 将首次查找的位置放入集合</span></span><br><span class="line">				list.add(mid);</span><br><span class="line"></span><br><span class="line">				<span class="comment">// 判断是否还有重复值</span></span><br><span class="line">				<span class="type">int</span> <span class="variable">index</span> <span class="operator">=</span> mid + <span class="number">1</span>;</span><br><span class="line">				<span class="keyword">while</span>(index &lt; arr.length)&#123;</span><br><span class="line">					<span class="keyword">if</span>(arr[index] == val)&#123;</span><br><span class="line">						list.add(index);</span><br><span class="line">					&#125;<span class="keyword">else</span>&#123;</span><br><span class="line">						<span class="keyword">break</span>;</span><br><span class="line">					&#125;</span><br><span class="line">					index++;</span><br><span class="line">				&#125;</span><br><span class="line">				index = mid-<span class="number">1</span>;</span><br><span class="line">				<span class="keyword">while</span>(index &gt;= <span class="number">0</span>)&#123;</span><br><span class="line">					<span class="keyword">if</span>(arr[index] == val)&#123;</span><br><span class="line">						list.add(index);</span><br><span class="line">					&#125;<span class="keyword">else</span>&#123;</span><br><span class="line">						<span class="keyword">break</span>;</span><br><span class="line">					&#125;</span><br><span class="line">					index--;</span><br><span class="line">				&#125;</span><br><span class="line">				<span class="keyword">return</span> list;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">return</span> <span class="literal">null</span>;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="comment">/**</span></span><br><span class="line"><span class="comment">	 * 有序的数组中查找某个元素出现的下标位置</span></span><br><span class="line"><span class="comment">	 * 使用递归的二分查找</span></span><br><span class="line"><span class="comment">	 * 返回出现的下标位置</span></span><br><span class="line"><span class="comment">	 */</span></span><br><span class="line">	<span class="keyword">public</span> <span class="keyword">static</span> <span class="type">int</span> <span class="title function_">recursionbinarySearch01</span><span class="params">(<span class="type">int</span>[] arr,<span class="type">int</span> low,<span class="type">int</span> high,<span class="type">int</span> val)</span>&#123;</span><br><span class="line"></span><br><span class="line">		<span class="keyword">if</span>(val &lt; arr[low] || val &gt; arr[high] || low &gt; high)&#123;</span><br><span class="line">			<span class="keyword">return</span> -<span class="number">1</span>;</span><br><span class="line">		&#125;</span><br><span class="line"></span><br><span class="line">		<span class="type">int</span> <span class="variable">mid</span> <span class="operator">=</span> (low + high)/<span class="number">2</span>;</span><br><span class="line"></span><br><span class="line">		<span class="keyword">if</span>(val &gt; arr[mid])&#123;</span><br><span class="line">			<span class="comment">//目标在右侧</span></span><br><span class="line">			<span class="keyword">return</span> recursionbinarySearch01(arr, mid+<span class="number">1</span>, high, val);</span><br><span class="line">		&#125;<span class="keyword">else</span> <span class="keyword">if</span>(val &lt; arr[mid])&#123;</span><br><span class="line">			<span class="comment">//目标在左侧</span></span><br><span class="line">			<span class="keyword">return</span> recursionbinarySearch01(arr, low, mid-<span class="number">1</span>, val);</span><br><span class="line">		&#125;<span class="keyword">else</span>&#123;</span><br><span class="line">			<span class="keyword">return</span> mid;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	</span><br><span class="line">	<span class="comment">/**</span></span><br><span class="line"><span class="comment">	 * 有序的数组中查找某个元素首次出现的下标位置</span></span><br><span class="line"><span class="comment">	 * 使用递归的二分查找</span></span><br><span class="line"><span class="comment">	 * 返回下标集合</span></span><br><span class="line"><span class="comment">	 */</span></span><br><span class="line">	<span class="keyword">public</span> <span class="keyword">static</span> List&lt;Integer&gt; <span class="title function_">recursionbinarySearch02</span><span class="params">(<span class="type">int</span>[] arr,<span class="type">int</span> low,<span class="type">int</span> high,<span class="type">int</span> val)</span>&#123;</span><br><span class="line"></span><br><span class="line">		<span class="keyword">if</span>(val &lt; arr[low] || val &gt; arr[high] || low &gt; high)&#123;</span><br><span class="line">			<span class="keyword">return</span> <span class="literal">null</span>;</span><br><span class="line">		&#125;</span><br><span class="line"></span><br><span class="line">		<span class="type">int</span> <span class="variable">mid</span> <span class="operator">=</span> (low + high)/<span class="number">2</span>;</span><br><span class="line"></span><br><span class="line">		<span class="keyword">if</span>(val &gt; arr[mid])&#123;</span><br><span class="line">			<span class="comment">//目标在右侧</span></span><br><span class="line">			<span class="keyword">return</span> recursionbinarySearch02(arr, mid+<span class="number">1</span>, high, val);</span><br><span class="line">		&#125;<span class="keyword">else</span> <span class="keyword">if</span>(val &lt; arr[mid])&#123;</span><br><span class="line">			<span class="comment">//目标在左侧</span></span><br><span class="line">			<span class="keyword">return</span> recursionbinarySearch02(arr, low, mid-<span class="number">1</span>, val);</span><br><span class="line">		&#125;<span class="keyword">else</span>&#123;</span><br><span class="line">			<span class="comment">// 定义放置索引下标的集合</span></span><br><span class="line">			List&lt;Integer&gt; list = <span class="keyword">new</span> <span class="title class_">ArrayList</span>&lt;&gt;();</span><br><span class="line">			<span class="comment">// 将首次查找的位置放入集合</span></span><br><span class="line">			list.add(mid);</span><br><span class="line"></span><br><span class="line">			<span class="comment">// 判断是否还有重复值</span></span><br><span class="line">			<span class="type">int</span> <span class="variable">index</span> <span class="operator">=</span> mid + <span class="number">1</span>;</span><br><span class="line">			<span class="keyword">while</span>(index &lt; arr.length)&#123;</span><br><span class="line">				<span class="keyword">if</span>(arr[index] == val)&#123;</span><br><span class="line">					list.add(index);</span><br><span class="line">				&#125;<span class="keyword">else</span>&#123;</span><br><span class="line">					<span class="keyword">break</span>;</span><br><span class="line">				&#125;</span><br><span class="line">				index++;</span><br><span class="line">			&#125;</span><br><span class="line">            </span><br><span class="line">			index = mid-<span class="number">1</span>;</span><br><span class="line">			<span class="keyword">while</span>(index &gt;= <span class="number">0</span>)&#123;</span><br><span class="line">				<span class="keyword">if</span>(arr[index] == val)&#123;</span><br><span class="line">					list.add(index);</span><br><span class="line">				&#125;<span class="keyword">else</span>&#123;</span><br><span class="line">					<span class="keyword">break</span>;</span><br><span class="line">				&#125;</span><br><span class="line">				index--;</span><br><span class="line">			&#125;</span><br><span class="line">			<span class="keyword">return</span> list;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h3 id="优缺点"><a href="#优缺点" class="headerlink" title="优缺点"></a>优缺点</h3><blockquote><p>优点:速度快，不占空间，不开辟新空间</p><p>缺点:必须是有序的数组，数据量太小没有意义</p></blockquote><h2 id="插值查找"><a href="#插值查找" class="headerlink" title="插值查找"></a>插值查找</h2><h3 id="概念-2"><a href="#概念-2" class="headerlink" title="概念"></a>概念</h3><blockquote><p>从折半查找中可以看出，折半查找的查找效率还是不错的。可是为什么要折半呢？为什么不是四分之一、八分之一呢？</p><p>打个比方，在牛津词典里要查找“apple”这个单词，会首先翻开字典的中间部分，然后继续折半吗？肯定不会，对于查找单词“apple”，我们肯定是下意识的往字典的最前部分翻去，而查找单词“zero”则相反，我们会下意识的往字典的最后部分翻去。</p><p>所以在折半查找法的基础上进行改造就出现了插值查找法，也叫做<strong>按比例查找</strong>。所以插值查找与折半查找唯一不同的是在于mid的计算方式上，它的计算方式为：</p><p>int mid &#x3D; low + (high - low) * (val- arr[low]) &#x2F; (arr[high] - arr[low])</p><p>这样就能快速定位目标数值所在的索引，比二分查找可以更快速实现查找。</p><p>自适应获取mid，也就是自适应查找点。</p></blockquote><h3 id="代码实现-2"><a href="#代码实现-2" class="headerlink" title="代码实现"></a>代码实现</h3><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br><span class="line">128</span><br><span class="line">129</span><br><span class="line">130</span><br><span class="line">131</span><br><span class="line">132</span><br><span class="line">133</span><br><span class="line">134</span><br><span class="line">135</span><br><span class="line">136</span><br><span class="line">137</span><br><span class="line">138</span><br><span class="line">139</span><br><span class="line">140</span><br><span class="line">141</span><br><span class="line">142</span><br><span class="line">143</span><br><span class="line">144</span><br><span class="line">145</span><br><span class="line">146</span><br><span class="line">147</span><br><span class="line">148</span><br><span class="line">149</span><br><span class="line">150</span><br><span class="line">151</span><br><span class="line">152</span><br><span class="line">153</span><br><span class="line">154</span><br><span class="line">155</span><br><span class="line">156</span><br><span class="line">157</span><br><span class="line">158</span><br><span class="line">159</span><br><span class="line">160</span><br><span class="line">161</span><br><span class="line">162</span><br><span class="line">163</span><br><span class="line">164</span><br><span class="line">165</span><br><span class="line">166</span><br><span class="line">167</span><br><span class="line">168</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">Test01</span> &#123;</span><br><span class="line">	<span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">main</span><span class="params">(String[] args)</span> &#123;</span><br><span class="line">		<span class="comment">//插值查找</span></span><br><span class="line">		</span><br><span class="line">		<span class="type">int</span>[] arr = &#123;<span class="number">1</span>,<span class="number">2</span>,<span class="number">3</span>,<span class="number">4</span>,<span class="number">5</span>,<span class="number">6</span>,<span class="number">7</span>,<span class="number">8</span>,<span class="number">9</span>,<span class="number">11</span>,<span class="number">11</span>,<span class="number">11</span>,<span class="number">11</span>,<span class="number">11</span>,<span class="number">11</span>&#125;;</span><br><span class="line"></span><br><span class="line">		<span class="type">int</span> <span class="variable">index</span> <span class="operator">=</span> insertSearch01(arr, <span class="number">11</span>);</span><br><span class="line">		System.out.println(<span class="string">&quot;指定元素出现的下标位置：&quot;</span> + index);</span><br><span class="line"></span><br><span class="line">		List&lt;Integer&gt; indexList = insertSearch02(arr, <span class="number">11</span>);</span><br><span class="line">		System.out.println(<span class="string">&quot;指定元素出现的下标位置的集合：&quot;</span> + Arrays.toString(indexList.toArray()));</span><br><span class="line"></span><br><span class="line">		index = recursionInsertSearch01(arr, <span class="number">0</span>, arr.length-<span class="number">1</span>, <span class="number">11</span>);</span><br><span class="line">		System.out.println(<span class="string">&quot;递归方式 - 指定元素出现的下标位置：&quot;</span> + index);</span><br><span class="line"></span><br><span class="line">		indexList = recursionInsertSearch02(arr, <span class="number">0</span>, arr.length-<span class="number">1</span>, <span class="number">11</span>);</span><br><span class="line">		System.out.println(<span class="string">&quot;递归方式 - 指定元素出现的下标位置的集合：&quot;</span> + Arrays.toString(indexList.toArray()));</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="comment">/**</span></span><br><span class="line"><span class="comment">	 * 有序的数组中查找某个元素出现的下标位置</span></span><br><span class="line"><span class="comment">	 * 不使用递归的二分查找</span></span><br><span class="line"><span class="comment">	 * 返回出现的下标位置</span></span><br><span class="line"><span class="comment">	 */</span></span><br><span class="line">	<span class="keyword">public</span> <span class="keyword">static</span> <span class="type">int</span> <span class="title function_">insertSearch01</span><span class="params">(<span class="type">int</span>[] arr,<span class="type">int</span> val)</span>&#123;</span><br><span class="line"></span><br><span class="line">		<span class="type">int</span> <span class="variable">low</span> <span class="operator">=</span> <span class="number">0</span>;</span><br><span class="line">		<span class="type">int</span> <span class="variable">high</span> <span class="operator">=</span> arr.length-<span class="number">1</span>;</span><br><span class="line"></span><br><span class="line">		<span class="keyword">while</span>(low &lt;= high)&#123;</span><br><span class="line">			</span><br><span class="line">			<span class="type">int</span> <span class="variable">mid</span> <span class="operator">=</span> low + (high - low) * (val - arr[low])/(arr[high] - arr[low]);</span><br><span class="line"></span><br><span class="line">			<span class="keyword">if</span>(val &gt; arr[mid])&#123;</span><br><span class="line">				<span class="comment">//目标在右侧</span></span><br><span class="line">				low = mid+<span class="number">1</span>;</span><br><span class="line">			&#125;<span class="keyword">else</span> <span class="keyword">if</span>(val &lt; arr[mid])&#123;</span><br><span class="line">				<span class="comment">//目标在左侧</span></span><br><span class="line">				high = mid-<span class="number">1</span>;</span><br><span class="line">			&#125;<span class="keyword">else</span>&#123;</span><br><span class="line">				<span class="keyword">return</span> mid;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">return</span> -<span class="number">1</span>;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="comment">/**</span></span><br><span class="line"><span class="comment">	 * 有序的数组中查找某个元素首次出现的下标位置</span></span><br><span class="line"><span class="comment">	 * 不使用递归的二分查找</span></span><br><span class="line"><span class="comment">	 * 返回下标集合</span></span><br><span class="line"><span class="comment">	 */</span></span><br><span class="line">	<span class="keyword">public</span> <span class="keyword">static</span> List&lt;Integer&gt; <span class="title function_">insertSearch02</span><span class="params">(<span class="type">int</span>[] arr,<span class="type">int</span> val)</span>&#123;</span><br><span class="line"></span><br><span class="line">		<span class="type">int</span> <span class="variable">low</span> <span class="operator">=</span> <span class="number">0</span>;</span><br><span class="line">		<span class="type">int</span> <span class="variable">high</span> <span class="operator">=</span> arr.length-<span class="number">1</span>;</span><br><span class="line"></span><br><span class="line">		<span class="keyword">while</span>(low &lt;= high)&#123;</span><br><span class="line">			<span class="type">int</span> <span class="variable">mid</span> <span class="operator">=</span> low + (high - low) * (val - arr[low])/(arr[high] - arr[low]);</span><br><span class="line"></span><br><span class="line">			<span class="keyword">if</span>(val &gt; arr[mid])&#123;</span><br><span class="line">				<span class="comment">//目标在右侧</span></span><br><span class="line">				low = mid+<span class="number">1</span>;</span><br><span class="line">			&#125;<span class="keyword">else</span> <span class="keyword">if</span>(val &lt; arr[mid])&#123;</span><br><span class="line">				<span class="comment">//目标在左侧</span></span><br><span class="line">				high = mid-<span class="number">1</span>;</span><br><span class="line">			&#125;<span class="keyword">else</span>&#123;</span><br><span class="line">				<span class="comment">// 定义放置索引下标的集合</span></span><br><span class="line">				List&lt;Integer&gt; list = <span class="keyword">new</span> <span class="title class_">ArrayList</span>&lt;&gt;();</span><br><span class="line">				<span class="comment">// 将首次查找的位置放入集合</span></span><br><span class="line">				list.add(mid);</span><br><span class="line"></span><br><span class="line">				<span class="comment">// 判断是否还有重复值</span></span><br><span class="line">				<span class="type">int</span> <span class="variable">index</span> <span class="operator">=</span> mid + <span class="number">1</span>;</span><br><span class="line">				<span class="keyword">while</span>(index &lt; arr.length)&#123;</span><br><span class="line">					<span class="keyword">if</span>(arr[index] == val)&#123;</span><br><span class="line">						list.add(index);</span><br><span class="line">					&#125;<span class="keyword">else</span>&#123;</span><br><span class="line">						<span class="keyword">break</span>;</span><br><span class="line">					&#125;</span><br><span class="line">					index++;</span><br><span class="line">				&#125;</span><br><span class="line">				index = mid-<span class="number">1</span>;</span><br><span class="line">				<span class="keyword">while</span>(index &gt;= <span class="number">0</span>)&#123;</span><br><span class="line">					<span class="keyword">if</span>(arr[index] == val)&#123;</span><br><span class="line">						list.add(index);</span><br><span class="line">					&#125;<span class="keyword">else</span>&#123;</span><br><span class="line">						<span class="keyword">break</span>;</span><br><span class="line">					&#125;</span><br><span class="line">					index--;</span><br><span class="line">				&#125;</span><br><span class="line">				<span class="keyword">return</span> list;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">return</span> <span class="literal">null</span>;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="comment">/**</span></span><br><span class="line"><span class="comment">	 * 有序的数组中查找某个元素出现的下标位置</span></span><br><span class="line"><span class="comment">	 * 使用递归的二分查找</span></span><br><span class="line"><span class="comment">	 * 返回出现的下标位置</span></span><br><span class="line"><span class="comment">	 */</span></span><br><span class="line">	<span class="keyword">public</span> <span class="keyword">static</span> <span class="type">int</span> <span class="title function_">recursionInsertSearch01</span><span class="params">(<span class="type">int</span>[] arr,<span class="type">int</span> low,<span class="type">int</span> high,<span class="type">int</span> val)</span>&#123;</span><br><span class="line"></span><br><span class="line">		<span class="keyword">if</span>(val &lt; arr[low] || val &gt; arr[high] || low &gt; high)&#123;</span><br><span class="line">			<span class="keyword">return</span> -<span class="number">1</span>;</span><br><span class="line">		&#125;</span><br><span class="line"></span><br><span class="line">		<span class="type">int</span> <span class="variable">mid</span> <span class="operator">=</span> low + (high - low) * (val - arr[low])/(arr[high] - arr[low]);</span><br><span class="line"></span><br><span class="line">		<span class="keyword">if</span>(val &gt; arr[mid])&#123;</span><br><span class="line">			<span class="comment">//目标在右侧</span></span><br><span class="line">			<span class="keyword">return</span> recursionInsertSearch01(arr, mid+<span class="number">1</span>, high, val);</span><br><span class="line">		&#125;<span class="keyword">else</span> <span class="keyword">if</span>(val &lt; arr[mid])&#123;</span><br><span class="line">			<span class="comment">//目标在左侧</span></span><br><span class="line">			<span class="keyword">return</span> recursionInsertSearch01(arr, low, mid-<span class="number">1</span>, val);</span><br><span class="line">		&#125;<span class="keyword">else</span>&#123;</span><br><span class="line">			<span class="keyword">return</span> mid;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	</span><br><span class="line">	<span class="comment">/**</span></span><br><span class="line"><span class="comment">	 * 有序的数组中查找某个元素首次出现的下标位置</span></span><br><span class="line"><span class="comment">	 * 使用递归的二分查找</span></span><br><span class="line"><span class="comment">	 * 返回下标集合</span></span><br><span class="line"><span class="comment">	 */</span></span><br><span class="line">	<span class="keyword">public</span> <span class="keyword">static</span> List&lt;Integer&gt; <span class="title function_">recursionInsertSearch02</span><span class="params">(<span class="type">int</span>[] arr,<span class="type">int</span> low,<span class="type">int</span> high,<span class="type">int</span> val)</span>&#123;</span><br><span class="line"></span><br><span class="line">		<span class="keyword">if</span>(val &lt; arr[low] || val &gt; arr[high] || low &gt; high)&#123;</span><br><span class="line">			<span class="keyword">return</span> <span class="literal">null</span>;</span><br><span class="line">		&#125;</span><br><span class="line"></span><br><span class="line">		<span class="type">int</span> <span class="variable">mid</span> <span class="operator">=</span> low + (high - low) * (val - arr[low])/(arr[high] - arr[low]);</span><br><span class="line"></span><br><span class="line">		<span class="keyword">if</span>(val &gt; arr[mid])&#123;</span><br><span class="line">			<span class="comment">//目标在右侧</span></span><br><span class="line">			<span class="keyword">return</span> recursionInsertSearch02(arr, mid+<span class="number">1</span>, high, val);</span><br><span class="line">		&#125;<span class="keyword">else</span> <span class="keyword">if</span>(val &lt; arr[mid])&#123;</span><br><span class="line">			<span class="comment">//目标在左侧</span></span><br><span class="line">			<span class="keyword">return</span> recursionInsertSearch02(arr, low, mid-<span class="number">1</span>, val);</span><br><span class="line">		&#125;<span class="keyword">else</span>&#123;</span><br><span class="line">			<span class="comment">// 定义放置索引下标的集合</span></span><br><span class="line">			List&lt;Integer&gt; list = <span class="keyword">new</span> <span class="title class_">ArrayList</span>&lt;&gt;();</span><br><span class="line">			<span class="comment">// 将首次查找的位置放入集合</span></span><br><span class="line">			list.add(mid);</span><br><span class="line"></span><br><span class="line">			<span class="comment">// 判断是否还有重复值</span></span><br><span class="line">			<span class="type">int</span> <span class="variable">index</span> <span class="operator">=</span> mid + <span class="number">1</span>;</span><br><span class="line">			<span class="keyword">while</span>(index &lt; arr.length)&#123;</span><br><span class="line">				<span class="keyword">if</span>(arr[index] == val)&#123;</span><br><span class="line">					list.add(index);</span><br><span class="line">				&#125;<span class="keyword">else</span>&#123;</span><br><span class="line">					<span class="keyword">break</span>;</span><br><span class="line">				&#125;</span><br><span class="line">				index++;</span><br><span class="line">			&#125;</span><br><span class="line">			index = mid-<span class="number">1</span>;</span><br><span class="line">			<span class="keyword">while</span>(index &gt;= <span class="number">0</span>)&#123;</span><br><span class="line">				<span class="keyword">if</span>(arr[index] == val)&#123;</span><br><span class="line">					list.add(index);</span><br><span class="line">				&#125;<span class="keyword">else</span>&#123;</span><br><span class="line">					<span class="keyword">break</span>;</span><br><span class="line">				&#125;</span><br><span class="line">				index--;</span><br><span class="line">			&#125;</span><br><span class="line">			<span class="keyword">return</span> list;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h2 id="斐波那契查找"><a href="#斐波那契查找" class="headerlink" title="斐波那契查找"></a>斐波那契查找</h2><h3 id="概念-3"><a href="#概念-3" class="headerlink" title="概念"></a>概念</h3><blockquote><p>斐波那契查找也叫做黄金分割法查找。</p><p>斐波那契查找也是二分查找的一种提升算法，通过运用黄金比例的概念在数列中选择查找点进行查找，提高查找效率。同样地，斐波那契查找也属于一种有序查找算法。</p></blockquote><h3 id="原理-1"><a href="#原理-1" class="headerlink" title="原理"></a>原理</h3><blockquote><p>对于斐波那契数列：1、1、2、3、5、8、13、21、34、55、89……（也可以从0开始），前后两个数字的比值随着数列的增加，越来越接近黄金比值0.618。</p><p>比如元素个数为89的有序列表。89在斐波那契数列中是34和55相加所得。</p><p>把元素个数为89的有序列表分成：前55个数据元素组成的前半段和34个数据元素组成的后半段。那么前半段元素个数和整个有序表长度的比值接近黄金比值0.618，而前后两段长度的比值也接近黄金比值0.618。</p><p>假如要查找的元素在前半段，那么继续按照斐波那契数列来看，55 &#x3D; 34 + 21，所以继续把前半段分成前34个数据元素的前半段和后21个元素的后半段，继续查找，如此反复，直到查找成功或失败。这样斐波那契数列就被应用到查找算法中了。</p><p>总长度&#x3D;f[k]，</p><p>前半段长度&#x3D;f[k-1]，后半段长度&#x3D;f[k-2]</p></blockquote><img src="https://image.insectmk.cn/hexo-gitee-blog/article/_post/education/qianfeng/day09-2/image-20220809223851707.png" alt="image-20220809223851707" style="zoom:80%"><blockquote><p>有序列表的元素个数不是斐波那契数列中的数字时该如何处理呢？</p><p>当有序表的元素个数不是斐波那契数列中的某个数字时，需要把有序列表的长度补齐，让它成为斐波那契数列中的一个数值。</p><p>如果不是补齐，而是将多余的截掉是否可行？把原有序列表截断肯定是不可行的，因为可能把要查找的目标值截掉。</p><p>每次取斐波那契数列中的某个值时(f[k])，都会进行-1操作，这是因为数组下标从0开始。</p></blockquote><h3 id="代码实现-3"><a href="#代码实现-3" class="headerlink" title="代码实现"></a>代码实现</h3><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">Test01</span> &#123;</span><br><span class="line">	<span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">main</span><span class="params">(String[] args)</span> &#123;</span><br><span class="line">		</span><br><span class="line">		<span class="type">int</span>[] arr = &#123;<span class="number">1</span>,<span class="number">13</span>,<span class="number">25</span>,<span class="number">37</span>,<span class="number">49</span>,<span class="number">51</span>,<span class="number">62</span>,<span class="number">68</span>,<span class="number">70</span>,<span class="number">80</span>,<span class="number">80</span>&#125;;</span><br><span class="line">		</span><br><span class="line">		List&lt;Integer&gt; fiboSearchList = fiboSearchList(arr, <span class="number">80</span>);</span><br><span class="line">		System.out.println(Arrays.toString(fiboSearchList.toArray()));</span><br><span class="line">	&#125;</span><br><span class="line">	</span><br><span class="line">	<span class="keyword">public</span> <span class="keyword">static</span> List&lt;Integer&gt; <span class="title function_">fiboSearchList</span><span class="params">(<span class="type">int</span>[] arr, <span class="type">int</span> val)</span> &#123;</span><br><span class="line">		</span><br><span class="line">		<span class="type">int</span> <span class="variable">low</span> <span class="operator">=</span> <span class="number">0</span>;</span><br><span class="line">		<span class="type">int</span> <span class="variable">high</span> <span class="operator">=</span> arr.length-<span class="number">1</span>;</span><br><span class="line">		</span><br><span class="line">		<span class="comment">// 斐波那契的索引下标。数组长度的数值在斐波那契数列中对应的索引下标</span></span><br><span class="line">		<span class="type">int</span>[] fiboArray = getFiboArray(<span class="number">10</span>);<span class="comment">//[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]</span></span><br><span class="line">		</span><br><span class="line">		<span class="comment">// 斐波那契的索引下标。数组长度的数值在斐波那契数列中对应的索引下标</span></span><br><span class="line">		<span class="type">int</span> <span class="variable">k</span> <span class="operator">=</span> <span class="number">0</span>;</span><br><span class="line">		<span class="comment">// 斐波那契的索引下标。数组长度的数值在斐波那契数列中对应的索引下标</span></span><br><span class="line">		<span class="keyword">while</span>(arr.length &gt; fiboArray[k])&#123;</span><br><span class="line">			k++;</span><br><span class="line">		&#125;</span><br><span class="line">		System.out.println(<span class="string">&quot;k = &quot;</span> + k);<span class="comment">//6</span></span><br><span class="line">		System.out.println(<span class="string">&quot;fiboArray = &quot;</span> + Arrays.toString(fiboArray));<span class="comment">//[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]</span></span><br><span class="line">		</span><br><span class="line">		<span class="comment">// 利用Java工具类Arrays 构造新数组并指向 数组 arr[]</span></span><br><span class="line">		<span class="type">int</span>[] temp = Arrays.copyOf(arr, fiboArray[k]);</span><br><span class="line">		System.out.println(<span class="string">&quot;temp=&quot;</span> + Arrays.toString(temp));</span><br><span class="line">        <span class="comment">//[1, 13, 25, 37, 49, 51, 62, 68, 70, 80, 80, 0, 0]</span></span><br><span class="line">		</span><br><span class="line">		<span class="comment">//对新构造的数组进行元素补充，补充为最高位的数值</span></span><br><span class="line">		<span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> high+<span class="number">1</span>; i &lt; temp.length; i++) &#123;</span><br><span class="line">			temp[i] = arr[high];</span><br><span class="line">		&#125;</span><br><span class="line">		System.out.println(<span class="string">&quot;补充数值的temp=&quot;</span> + Arrays.toString(temp));</span><br><span class="line">        <span class="comment">//[1, 13, 25, 37, 49, 51, 62, 68, 70, 80, 80, 80, 80]</span></span><br><span class="line">		</span><br><span class="line">		<span class="keyword">while</span>(low &lt;= high)&#123;</span><br><span class="line">			</span><br><span class="line">			<span class="comment">//数列左侧有f[k-1]个元素</span></span><br><span class="line">			<span class="type">int</span> <span class="variable">mid</span> <span class="operator">=</span> low + fiboArray[k-<span class="number">1</span>] - <span class="number">1</span>;</span><br><span class="line">			</span><br><span class="line">			<span class="keyword">if</span>(val &lt; temp[mid])&#123;</span><br><span class="line">				<span class="comment">// 目标值小于mid所在元素，在左侧查找</span></span><br><span class="line">				high = mid-<span class="number">1</span>;</span><br><span class="line">				</span><br><span class="line">				<span class="comment">/*全部元素=前部元素+后部元素</span></span><br><span class="line"><span class="comment">                 * f[k]=f[k-1]+f[k-2]</span></span><br><span class="line"><span class="comment">                 * 因为左侧有f[k-1]个元素，所以可以继续拆分f[k-1]=f[k-2]+f[k-3]</span></span><br><span class="line"><span class="comment">                 * 即在f[k-1]的前部继续查找 所以k-=1</span></span><br><span class="line"><span class="comment">                 * 即下次循环 mid=f[k-1-1]-1</span></span><br><span class="line"><span class="comment">                 */</span></span><br><span class="line">				k-=<span class="number">1</span>;</span><br><span class="line">			&#125;<span class="keyword">else</span> <span class="keyword">if</span>(val &gt; temp[mid])&#123;</span><br><span class="line">				<span class="comment">// 目标值大于mid所在元素，在右侧查找</span></span><br><span class="line">				low = mid+<span class="number">1</span>;</span><br><span class="line">				</span><br><span class="line">				<span class="comment">/*全部元素=前部元素+后部元素</span></span><br><span class="line"><span class="comment">                 * f[k]=f[k-1]+f[k-2]</span></span><br><span class="line"><span class="comment">                 * 因为右侧有f[k-2]个元素，所以可以继续拆分f[k-2]=f[k-3]+f[k-4]</span></span><br><span class="line"><span class="comment">                 * 即在f[k-2]的前部继续查找 所以k-=2</span></span><br><span class="line"><span class="comment">                 * 即下次循环 mid=f[k-1-2]-1</span></span><br><span class="line"><span class="comment">               	 */</span></span><br><span class="line">				k -= <span class="number">2</span>;</span><br><span class="line">				</span><br><span class="line">			&#125;<span class="keyword">else</span>&#123;</span><br><span class="line">				</span><br><span class="line">				<span class="comment">// 定义放置索引下标的集合</span></span><br><span class="line">				ArrayList&lt;Integer&gt; list = <span class="keyword">new</span> <span class="title class_">ArrayList</span>&lt;&gt;();</span><br><span class="line">				list.add(mid);</span><br><span class="line">				</span><br><span class="line">				<span class="type">int</span> <span class="variable">index</span> <span class="operator">=</span> mid+<span class="number">1</span>;</span><br><span class="line">				<span class="keyword">while</span>(index &lt; arr.length)&#123;</span><br><span class="line">					<span class="keyword">if</span>(arr[index] == val)&#123;</span><br><span class="line">						list.add(index);</span><br><span class="line">						index++;</span><br><span class="line">					&#125;<span class="keyword">else</span>&#123;</span><br><span class="line">						<span class="keyword">break</span>;</span><br><span class="line">					&#125;</span><br><span class="line">				&#125;</span><br><span class="line">				index = mid-<span class="number">1</span>;</span><br><span class="line">				<span class="keyword">while</span>(index &gt; <span class="number">0</span>)&#123;</span><br><span class="line">					<span class="keyword">if</span>(arr[index] == val)&#123;</span><br><span class="line">						list.add(index);</span><br><span class="line">						index--;</span><br><span class="line">					&#125;<span class="keyword">else</span>&#123;</span><br><span class="line">						<span class="keyword">break</span>;</span><br><span class="line">					&#125;</span><br><span class="line">				&#125;</span><br><span class="line">				<span class="keyword">return</span> list;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">return</span> <span class="literal">null</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	</span><br><span class="line">	<span class="keyword">public</span> <span class="keyword">static</span> <span class="type">int</span>[] getFiboArray(<span class="type">int</span> maxSize)&#123;</span><br><span class="line">		</span><br><span class="line">		<span class="type">int</span>[] fiboArray = <span class="keyword">new</span> <span class="title class_">int</span>[maxSize];</span><br><span class="line">		</span><br><span class="line">		fiboArray[<span class="number">0</span>] = <span class="number">1</span>;</span><br><span class="line">		fiboArray[<span class="number">1</span>] = <span class="number">1</span>;</span><br><span class="line">		</span><br><span class="line">		<span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">2</span>; i &lt; fiboArray.length; i++) &#123;</span><br><span class="line">			fiboArray[i] = fiboArray[i-<span class="number">1</span>] + fiboArray[i-<span class="number">2</span>];</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">return</span> fiboArray;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></article><div class="post-copyright"><div class="copyright-cc-box"><i class="anzhiyufont anzhiyu-icon-copyright"></i></div><div class="post-copyright__author_box"><a class="post-copyright__author_img" target="_blank" rel="noopener" href="https://insectmk.cn" title="头像"><img class="post-copyright__author_img_back" src="/static/img/head/insectmk.jpg" title="头像" alt="头像"><img class="post-copyright__author_img_front" src="/static/img/head/insectmk.jpg" title="头像" alt="头像"></a><div class="post-copyright__author_name">InsectMk</div><div class="post-copyright__author_desc">今天特别开心！</div></div><div class="post-copyright__post__info"><a class="post-copyright__original" title="该文章为原创文章，注意版权协议" href="https://insectmk.top/posts/8eef9745/">原创</a><a class="post-copyright-title"><span onclick='rm.copyPageUrl("https://insectmk.top/posts/8eef9745/")'>数组的查找</span></a></div><div class="post-tools" id="post-tools"><div class="post-tools-left"><div class="rewardLeftButton"></div><div class="shareRight"><div class="share-link mobile"><div class="share-qrcode"><div class="share-button" title="使用手机访问这篇文章"><i class="anzhiyufont anzhiyu-icon-qrcode"></i></div><div class="share-main"><div class="share-main-all"><div id="qrcode" title="https://insectmk.top/posts/8eef9745/"></div><div class="reward-dec">使用手机访问这篇文章</div></div></div></div></div><div class="share-link weibo"><a class="share-button" target="_blank" href="https://service.weibo.com/share/share.php?title=undefined&amp;url=https://insectmk.top/posts/8eef9745/&amp;pic=undefined" rel="external nofollow noreferrer noopener"><i class="anzhiyufont anzhiyu-icon-weibo"></i></a></div><script>function copyCurrentPageUrl(){var e=window.location.href,t=document.createElement("input");t.setAttribute("value",e),document.body.appendChild(t),t.select(),t.setSelectionRange(0,99999),document.execCommand("copy"),document.body.removeChild(t)}</script><div class="share-link copyurl"><div class="share-button" id="post-share-url" title="复制链接" onclick="copyCurrentPageUrl()"><i class="anzhiyufont anzhiyu-icon-link"></i></div></div></div></div></div><div class="post-copyright__notice"><span class="post-copyright-info">本博客所有文章除特别声明外，均采用 <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/" target="_blank">CC BY-NC-SA 4.0</a> 许可协议。转载请注明来自 <a href="https://insectmk.top" target="_blank">InsectMk的个人空间</a>！</span></div></div><div class="post-tools-right"><div class="tag_share"><div class="post-meta__box"><div class="post-meta__box__tag-list"><a class="post-meta__box__tags" href="/tags/Java/"><span class="tags-punctuation"><i class="anzhiyufont anzhiyu-icon-tag"></i></span>Java<span class="tagsPageCount">35</span></a><a class="post-meta__box__tags" href="/tags/%E5%8D%83%E9%94%8B%E6%95%99%E8%82%B2/"><span class="tags-punctuation"> <i class="anzhiyufont anzhiyu-icon-tag"></i></span>千锋教育<span class="tagsPageCount">30</span></a><a class="post-meta__box__tags" href="/tags/%E5%9F%B9%E8%AE%AD/"><span class="tags-punctuation"> <i class="anzhiyufont anzhiyu-icon-tag"></i></span>培训<span class="tagsPageCount">30</span></a></div></div></div><div class="post_share"><div class="social-share" data-image="https://image.insectmk.cn/hexo-gitee-blog/cover/github-insectmk.jpg" data-sites="facebook,twitter,wechat,weibo,qq"></div><link rel="stylesheet" href="https://cdn.cbd.int/butterfly-extsrc@1.1.3/sharejs/dist/css/share.min.css" media="print" onload='this.media="all"'><script src="https://cdn.cbd.int/butterfly-extsrc@1.1.3/sharejs/dist/js/social-share.min.js" defer></script></div></div><nav class="pagination-post" id="pagination"><div class="prev-post pull-left"><a href="/posts/ad01bc3e/"><img class="prev-cover" src="/" onerror='onerror=null,src="/static/img/website/404.jpg"' alt="cover of previous post"><div class="pagination-info"><div class="label">上一篇</div><div class="prev_info">方法</div></div></a></div><div class="next-post pull-right"><a href="/posts/1a656c15/"><img class="next-cover" src="/" onerror='onerror=null,src="/static/img/website/404.jpg"' alt="cover of next post"><div class="pagination-info"><div class="label">下一篇</div><div class="next_info">数据的排序</div></div></a></div></nav><div class="relatedPosts"><div class="headline"><i class="anzhiyufont anzhiyu-icon-thumbs-up fa-fw" style="font-size:1.5rem;margin-right:4px"></i><span>喜欢这篇文章的人也看了</span></div><div class="relatedPosts-list"><div><a href="/posts/b51f2d85/" title="动&#x2F;静态语言、强&#x2F;弱类型语言、编译型&#x2F;解释形语言的区别"><img class="cover" src="/" alt="cover"><div class="content is-center"><div class="date"><i class="anzhiyufont anzhiyu-icon-calendar-days fa-fw"></i> 2023-06-26</div><div class="title">动&#x2F;静态语言、强&#x2F;弱类型语言、编译型&#x2F;解释形语言的区别</div></div></a></div><div><a href="/posts/836f8ca6/" title="千锋JavaDay01"><img class="cover" src="/" alt="cover"><div class="content is-center"><div class="date"><i class="anzhiyufont anzhiyu-icon-calendar-days fa-fw"></i> 2023-06-26</div><div class="title">千锋JavaDay01</div></div></a></div><div><a href="/posts/f9fe4650/" title="主方法的构造"><img class="cover" src="/" alt="cover"><div class="content is-center"><div class="date"><i class="anzhiyufont anzhiyu-icon-calendar-days fa-fw"></i> 2023-06-26</div><div class="title">主方法的构造</div></div></a></div><div><a href="/posts/1a66dd1c/" title="千锋JavaDay02"><img class="cover" src="/" alt="cover"><div class="content is-center"><div class="date"><i class="anzhiyufont anzhiyu-icon-calendar-days fa-fw"></i> 2023-06-26</div><div class="title">千锋JavaDay02</div></div></a></div><div><a href="/posts/d88f5f05/" title="字节码文件解析"><img class="cover" src="/" alt="cover"><div class="content is-center"><div class="date"><i class="anzhiyufont anzhiyu-icon-calendar-days fa-fw"></i> 2023-06-26</div><div class="title">字节码文件解析</div></div></a></div><div><a href="/posts/18c98bc7/" title="深入乱码"><img class="cover" src="/" alt="cover"><div class="content is-center"><div class="date"><i class="anzhiyufont anzhiyu-icon-calendar-days fa-fw"></i> 2023-06-26</div><div class="title">深入乱码</div></div></a></div></div></div><hr><div id="post-comment"><div class="comment-head"><div class="comment-headline"><i class="anzhiyufont anzhiyu-icon-comments"></i><span> 评论</span></div><div class="comment-randomInfo"><a onclick="anzhiyu.addRandomCommentInfo()" href="javascript:void(0)">匿名评论</a><a href="/privacy" style="margin-left:4px">隐私政策</a></div></div><div class="comment-wrap"><div><div id="waline-wrap"></div></div></div></div><div class="comment-barrage"></div></div><div class="aside-content" id="aside-content"><div class="card-widget card-info"><div class="card-content"><div class="author-info-avatar"><img class="avatar-img" src="/static/img/head/insectmk.jpg" onerror='this.onerror=null,this.src="/static/img/website/friend_404.gif"' alt="avatar"></div><div class="author-info__description"><div style="line-height:1.38;margin:.6rem 0;text-align:justify;color:rgba(255,255,255,.8)">这有关于<b style="color:#fff">程序开发、部署</b>相关的问题和看法，还有<b style="color:#fff">软件推荐</b>和<b style="color:#fff">分享</b>。</div><div style="line-height:1.38;margin:.6rem 0;text-align:justify;color:rgba(255,255,255,.8)">相信你可以在这里找到对你有用的<b style="color:#fff">知识</b>和<b style="color:#fff">教程</b>。</div></div><div class="author-info__bottom-group"><a class="author-info__bottom-group-left" href="/"><h1 class="author-info__name">InsectMk</h1><div class="author-info__desc">今天特别开心！</div></a><div class="card-info-social-icons is-center"><a class="social-icon faa-parent animated-hover" href="https://gitee.com/insectmk" target="_blank" title="Gitee"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-gitee"></use></svg></a><a class="social-icon faa-parent animated-hover" href="/static/img/website/contact/qq.png" target="_blank" title="QQ"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-qq"></use></svg></a><a class="social-icon faa-parent animated-hover" href="/static/img/website/contact/wechat.png" target="_blank" title="WeChat"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-wechat"></use></svg></a><a class="social-icon faa-parent animated-hover" href="/atom.xml" target="_blank" title="订阅-ATOM"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-rss"></use></svg></a><a class="social-icon faa-parent animated-hover" href="mailto:3067836615@qq.com" target="_blank" title="Email"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-youxiang-"></use></svg></a></div></div></div></div><div class="sticky_layout"><div class="card-widget" id="card-toc"><div class="item-headline"><i class="anzhiyufont anzhiyu-icon-bars"></i><span>文章目录</span><span class="toc-percentage"></span></div><div class="toc-content"><ol class="toc"><li class="toc-item toc-level-1"><a class="toc-link" href="#%E6%95%B0%E7%BB%84%E7%9A%84%E6%9F%A5%E6%89%BE"><span class="toc-number">1.</span> <span class="toc-text">数组的查找</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E7%BA%BF%E6%80%A7%E6%9F%A5%E6%89%BE"><span class="toc-number">1.1.</span> <span class="toc-text">线性查找</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%A6%82%E5%BF%B5"><span class="toc-number">1.1.1.</span> <span class="toc-text">概念</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0"><span class="toc-number">1.1.2.</span> <span class="toc-text">代码实现</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%BA%8C%E5%88%86%E6%B3%95%E6%9F%A5%E6%89%BE"><span class="toc-number">1.2.</span> <span class="toc-text">二分法查找</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%A6%82%E5%BF%B5-1"><span class="toc-number">1.2.1.</span> <span class="toc-text">概念</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%8E%9F%E7%90%86"><span class="toc-number">1.2.2.</span> <span class="toc-text">原理</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0-1"><span class="toc-number">1.2.3.</span> <span class="toc-text">代码实现</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E4%BC%98%E7%BC%BA%E7%82%B9"><span class="toc-number">1.2.4.</span> <span class="toc-text">优缺点</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%8F%92%E5%80%BC%E6%9F%A5%E6%89%BE"><span class="toc-number">1.3.</span> <span class="toc-text">插值查找</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%A6%82%E5%BF%B5-2"><span class="toc-number">1.3.1.</span> <span class="toc-text">概念</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0-2"><span class="toc-number">1.3.2.</span> <span class="toc-text">代码实现</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%9F%A5%E6%89%BE"><span class="toc-number">1.4.</span> <span class="toc-text">斐波那契查找</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%A6%82%E5%BF%B5-3"><span class="toc-number">1.4.1.</span> <span class="toc-text">概念</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%8E%9F%E7%90%86-1"><span class="toc-number">1.4.2.</span> <span class="toc-text">原理</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0-3"><span class="toc-number">1.4.3.</span> <span class="toc-text">代码实现</span></a></li></ol></li></ol></li></ol></div></div><div class="card-widget card-recent-post"><div class="item-headline"><i class="anzhiyufont anzhiyu-icon-history"></i><span>最近发布</span></div><div class="aside-list"><div class="aside-list-item"><a class="thumbnail" href="/posts/98f3f974/" title="美化你的Github个人主页"><img src="https://image.insectmk.cn/hexo-gitee-blog/cover/github-insectmk.jpg" onerror='this.onerror=null,this.src="/static/img/website/404.jpg"' alt="美化你的Github个人主页"></a><div class="content"><a class="title" href="/posts/98f3f974/" title="美化你的Github个人主页">美化你的Github个人主页</a><time datetime="2024-07-30T02:52:23.000Z" title="发表于 2024-07-30 10:52:23">2024-07-30</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/posts/10d64ca8/" title="我的Hexo博客多主题同时部署的实现思路（Butterfly+安知鱼）"><img src="https://image.insectmk.cn/hexo-gitee-blog/cover/hexo-butterfly.jpg" onerror='this.onerror=null,this.src="/static/img/website/404.jpg"' alt="我的Hexo博客多主题同时部署的实现思路（Butterfly+安知鱼）"></a><div class="content"><a class="title" href="/posts/10d64ca8/" title="我的Hexo博客多主题同时部署的实现思路（Butterfly+安知鱼）">我的Hexo博客多主题同时部署的实现思路（Butterfly+安知鱼）</a><time datetime="2024-07-30T01:30:07.000Z" title="发表于 2024-07-30 09:30:07">2024-07-30</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/posts/129b7f4a/" title="使用Spring AI对接Ollama搭建自己的智能问答网站"><img src="https://image.insectmk.cn/hexo-gitee-blog/cover/ollama.jpg" onerror='this.onerror=null,this.src="/static/img/website/404.jpg"' alt="使用Spring AI对接Ollama搭建自己的智能问答网站"></a><div class="content"><a class="title" href="/posts/129b7f4a/" title="使用Spring AI对接Ollama搭建自己的智能问答网站">使用Spring AI对接Ollama搭建自己的智能问答网站</a><time datetime="2024-07-20T02:45:24.000Z" title="发表于 2024-07-20 10:45:24">2024-07-20</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/posts/9c83ed78/" title="无需更改源码！让你的Hexo的文章在首页隐藏"><img src="https://image.insectmk.cn/hexo-gitee-blog/cover/hexo-hide-posts.jpg" onerror='this.onerror=null,this.src="/static/img/website/404.jpg"' alt="无需更改源码！让你的Hexo的文章在首页隐藏"></a><div class="content"><a class="title" href="/posts/9c83ed78/" title="无需更改源码！让你的Hexo的文章在首页隐藏">无需更改源码！让你的Hexo的文章在首页隐藏</a><time datetime="2024-07-19T02:22:45.000Z" title="发表于 2024-07-19 10:22:45">2024-07-19</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/posts/9348d5be/" title="使用Cloudflare加速Docker镜像下载"><img src="https://image.insectmk.cn/hexo-gitee-blog/cover/docker.png" onerror='this.onerror=null,this.src="/static/img/website/404.jpg"' alt="使用Cloudflare加速Docker镜像下载"></a><div class="content"><a class="title" href="/posts/9348d5be/" title="使用Cloudflare加速Docker镜像下载">使用Cloudflare加速Docker镜像下载</a><time datetime="2024-06-13T08:01:10.000Z" title="发表于 2024-06-13 16:01:10">2024-06-13</time></div></div></div></div></div></div></div></main><footer id="footer"><div id="footer-wrap"><div id="workboard"><div id="runtimeTextTip"></div></div><p id="ghbdages"><a class="github-badge" target="_blank" href="https://hexo.io/" style="margin-inline:5px" data-title="博客框架为Hexo_v7.3.0" title="博客框架为Hexo_v7.3.0"><img src="https://npm.elemecdn.com/anzhiyu-blog@2.1.5/img/badge/Frame-Hexo.svg" alt="博客框架为Hexo_v7.3.0"></a><a class="github-badge" target="_blank" href="https://blog.anheyu.com/" style="margin-inline:5px" data-title="本站使用AnZhiYu主题" title="本站使用AnZhiYu主题"><img src="https://npm.elemecdn.com/anzhiyu-theme-static@1.0.9/img/Theme-AnZhiYu-2E67D3.svg" alt="本站使用AnZhiYu主题"></a></p></div><div id="footer-bar"><div class="footer-bar-links"><div class="footer-bar-left"><div id="footer-bar-tips"><div class="copyright">&copy;2020 - 2024 By <a class="footer-bar-link" href="/" title="InsectMk" target="_blank">InsectMk</a></div></div><div id="footer-type-tips"></div></div><div class="footer-bar-right"><a class="footer-bar-link" target="_blank" rel="noopener" href="https://github.com/anzhiyu-c/hexo-theme-anzhiyu" title="主题">主题</a><a class="footer-bar-link" target="_blank" rel="noopener" href="https://beian.miit.gov.cn/" title="蜀ICP备2023013851号-2">蜀ICP备2023013851号-2</a><a class="footer-bar-link" target="_blank" rel="noopener" href="https://beian.mps.gov.cn/#/query/webSearch?code=51142202000154" title="川公网安备51142202000154号">川公网安备51142202000154号</a></div></div></div></footer></div><div id="sidebar"><div id="menu-mask"></div><div id="sidebar-menus"><div class="sidebar-site-data site-data is-center"><a href="/archives/" title="archive"><div class="headline">文章</div><div class="length-num">121</div></a><a href="/tags/" title="tag"><div class="headline">标签</div><div class="length-num">117</div></a><a href="/categories/" title="category"><div class="headline">分类</div><div class="length-num">14</div></a></div><span class="sidebar-menu-item-title">功能</span><div class="sidebar-menu-item"><a class="darkmode_switchbutton menu-child" href="javascript:void(0);" title="显示模式"><i class="anzhiyufont anzhiyu-icon-circle-half-stroke"></i><span>显示模式</span></a></div><div class="back-menu-list-groups"><div class="back-menu-list-group"><div class="back-menu-list-title">网页</div><div class="back-menu-list"><a class="back-menu-item" target="_blank" rel="noopener" href="https://insectmk.cn/" title="主博客"><img class="back-menu-item-icon" src="/static/img/website/favicon.jpg" alt="主博客"><span class="back-menu-item-text">主博客</span></a><a class="back-menu-item" href="https://insectmk.top/" title="次博客"><img class="back-menu-item-icon" src="/static/img/website/favicon.jpg" alt="次博客"><span class="back-menu-item-text">次博客</span></a></div></div><div class="back-menu-list-group"><div class="back-menu-list-title">项目</div><div class="back-menu-list"><a class="back-menu-item" target="_blank" rel="noopener" href="https://gitee.com/insectmk/chatbot-web" title="智能聊天机器人网站"><img class="back-menu-item-icon" src="https://image.insectmk.cn/hexo-gitee-blog/project/icon/chatbot-web.jpg" alt="智能聊天机器人网站"><span class="back-menu-item-text">智能聊天机器人网站</span></a></div></div></div><div class="menus_items"><div class="menus_item"><a class="site-page faa-parent animated-hover" href="/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-home"></use></svg><span>主页</span></a></div><div class="menus_item"><a class="site-page" href="javascript:void(0);"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-hand-peace"></use></svg><span>娱乐</span></a><ul class="menus_item_child"><li><a class="site-page child faa-parent animated-hover" href="/entertainment/gallery/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-images"></use></svg><span>图库</span></a></li></ul></div><div class="menus_item"><a class="site-page" href="javascript:void(0);"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-comments"></use></svg><span>交流</span></a><ul class="menus_item_child"><li><a class="site-page child faa-parent animated-hover" href="/contact/comments/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-paper-plane"></use></svg><span>留言板</span></a></li><li><a class="site-page child faa-parent animated-hover" href="/contact/link/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-link"></use></svg><span>友链</span></a></li></ul></div><div class="menus_item"><a class="site-page" href="javascript:void(0);"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-compass"></use></svg><span>目录</span></a><ul class="menus_item_child"><li><a class="site-page child faa-parent animated-hover" href="/categories/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-archive"></use></svg><span>分类</span></a></li><li><a class="site-page child faa-parent animated-hover" href="/tags/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-tags"></use></svg><span>标签</span></a></li><li><a class="site-page child faa-parent animated-hover" href="/archives/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-folder-open"></use></svg><span>归档</span></a></li></ul></div><div class="menus_item"><a class="site-page" href="javascript:void(0);"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-server"></use></svg><span>服务</span></a><ul class="menus_item_child"><li><a class="site-page child faa-parent animated-hover" href="/server/left4dead2/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-icons-left__dead_"></use></svg><span>求生之路</span></a></li><li><a class="site-page child faa-parent animated-hover" href="/server/minecraft/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-minecraft"></use></svg><span>我的世界</span></a></li></ul></div><div class="menus_item"><a class="site-page" href="javascript:void(0);"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-clipboard"></use></svg><span>日志</span></a><ul class="menus_item_child"><li><a class="site-page child faa-parent animated-hover" href="/log/website/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-website-with-different-sections"></use></svg><span>个人网站</span></a></li><li><a class="site-page child faa-parent animated-hover" href="/log/pc/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-desktop"></use></svg><span>个人电脑</span></a></li></ul></div><div class="menus_item"><a class="site-page" href="javascript:void(0);"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-bars"></use></svg><span>其他</span></a><ul class="menus_item_child"><li><a class="site-page child faa-parent animated-hover" href="/extend/remind/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-note"></use></svg><span>备忘</span></a></li></ul></div><div class="menus_item"><a class="site-page faa-parent animated-hover" href="/about/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-id-card"></use></svg><span>关于</span></a></div></div><span class="sidebar-menu-item-title">标签</span><div class="card-tags"><div class="item-headline"></div><div class="card-tag-cloud"><a href="/tags/AOP/" style="font-size:.88rem">AOP<sup>1</sup></a><a href="/tags/Butterfly/" style="font-size:.88rem">Butterfly<sup>4</sup></a><a href="/tags/Docker/" style="font-size:.88rem">Docker<sup>6</sup></a><a href="/tags/ElementUI/" style="font-size:.88rem">ElementUI<sup>1</sup></a><a href="/tags/Frp/" style="font-size:.88rem">Frp<sup>1</sup></a><a href="/tags/Hexo/" style="font-size:.88rem;font-weight:500;color:var(--anzhiyu-lighttext)">Hexo<sup>8</sup></a><a href="/tags/IntelliJ-IDEA/" style="font-size:.88rem">IntelliJ IDEA<sup>1</sup></a><a href="/tags/JDK/" style="font-size:.88rem">JDK<sup>1</sup></a><a href="/tags/JWT/" style="font-size:.88rem">JWT<sup>1</sup></a><a href="/tags/Java/" style="font-size:.88rem">Java<sup>35</sup></a><a href="/tags/Junit/" style="font-size:.88rem">Junit<sup>1</sup></a><a href="/tags/Leanote/" style="font-size:.88rem">Leanote<sup>1</sup></a><a href="/tags/Maven/" style="font-size:.88rem">Maven<sup>2</sup></a><a href="/tags/MyBatisPlus/" style="font-size:.88rem">MyBatisPlus<sup>1</sup></a><a href="/tags/MySQL5-7/" style="font-size:.88rem">MySQL5.7<sup>1</sup></a><a href="/tags/Mybatis/" style="font-size:.88rem">Mybatis<sup>1</sup></a><a href="/tags/MybatisPlus/" style="font-size:.88rem">MybatisPlus<sup>1</sup></a><a href="/tags/OSS/" style="font-size:.88rem">OSS<sup>1</sup></a><a href="/tags/Spring/" style="font-size:.88rem">Spring<sup>2</sup></a><a href="/tags/Spring-Boot/" style="font-size:.88rem">SpringBoot<sup>6</sup></a><a href="/tags/Vue2/" style="font-size:.88rem">Vue2<sup>9</sup></a><a href="/tags/Vue3/" style="font-size:.88rem">Vue3<sup>1</sup></a><a href="/tags/Vuetify/" style="font-size:.88rem">Vuetify<sup>1</sup></a><a href="/tags/Vuex/" style="font-size:.88rem">Vuex<sup>1</sup></a><a href="/tags/Waline/" style="font-size:.88rem">Waline<sup>3</sup></a><a href="/tags/mvc/" style="font-size:.88rem">mvc<sup>3</sup></a><a href="/tags/mybatis/" style="font-size:.88rem">mybatis<sup>1</sup></a><a href="/tags/profile/" style="font-size:.88rem">profile<sup>1</sup></a><a href="/tags/spring/" style="font-size:.88rem">spring<sup>5</sup></a><a href="/tags/springboot/" style="font-size:.88rem">springboot<sup>4</sup></a><a href="/tags/transaction/" style="font-size:.88rem">transaction<sup>1</sup></a><a href="/tags/yaml/" style="font-size:.88rem">yaml<sup>2</sup></a><a href="/tags/%E4%B8%AA%E4%BA%BA%E5%8D%9A%E5%AE%A2/" style="font-size:.88rem">个人博客<sup>11</sup></a><a href="/tags/%E4%BA%8B%E5%8A%A1/" style="font-size:.88rem">事务<sup>1</sup></a><a href="/tags/%E5%88%86%E9%A1%B5/" style="font-size:.88rem">分页<sup>1</sup></a><a href="/tags/%E5%89%8D%E7%AB%AF/" style="font-size:.88rem;font-weight:500;color:var(--anzhiyu-lighttext)">前端<sup>1</sup></a><a href="/tags/%E6%9C%8D%E5%8A%A1%E5%99%A8/" style="font-size:.88rem">服务器<sup>20</sup></a><a href="/tags/%E6%AF%95%E4%B8%9A%E8%AE%BE%E8%AE%A1/" style="font-size:.88rem">毕业设计<sup>14</sup></a><a href="/tags/%E7%A6%85%E9%81%93/" style="font-size:.88rem">禅道<sup>1</sup></a><a href="/tags/%E7%BB%BF%E8%89%B2%E8%A7%A3%E5%8E%8B/" style="font-size:.88rem">绿色解压<sup>1</sup></a></div></div><hr></div></div><div id="rightside"><div id="rightside-config-hide"><button id="readmode" type="button" title="阅读模式"><i class="anzhiyufont anzhiyu-icon-book-open"></i></button><button id="translateLink" type="button" title="简繁转换">繁</button><button id="darkmode" type="button" title="浅色和深色模式转换"><i class="anzhiyufont anzhiyu-icon-circle-half-stroke"></i></button><button id="hide-aside-btn" type="button" title="单栏和双栏切换"><i class="anzhiyufont anzhiyu-icon-arrows-left-right"></i></button></div><div id="rightside-config-show"><button id="rightside-config" type="button" title="设置"><i class="anzhiyufont anzhiyu-icon-gear"></i></button><button class="close" id="mobile-toc-button" type="button" title="目录"><i class="anzhiyufont anzhiyu-icon-list-ul"></i></button><button id="chat-btn" type="button" title="聊天"><i class="anzhiyufont anzhiyu-icon-comment-sms"></i></button><a id="to_comment" href="#post-comment" title="直达评论"><i class="anzhiyufont anzhiyu-icon-comments"></i></a><button id="go-up" type="button" title="回到顶部"><i class="anzhiyufont anzhiyu-icon-arrow-up"></i></button></div></div><div id="nav-music"><a id="nav-music-hoverTips" onclick="anzhiyu.musicToggle()" accesskey="m">播放音乐</a><div id="console-music-bg"></div><meting-js id="975968032" server="netease" type="playlist" mutex="true" preload="none" theme="var(--anzhiyu-main)" data-lrctype="0" order="random" volume="0.7"></meting-js></div><div id="local-search"><div class="search-dialog"><nav class="search-nav"><span class="search-dialog-title">搜索</span><span id="loading-status"></span><button class="search-close-button"><i class="anzhiyufont anzhiyu-icon-xmark"></i></button></nav><div class="is-center" id="loading-database"><i class="anzhiyufont anzhiyu-icon-spinner anzhiyu-pulse-icon"></i><span> 数据库加载中</span></div><div class="search-wrap"><div id="local-search-input"><div class="local-search-box"><input class="local-search-box--input" placeholder="搜索文章" type="text"></div></div><hr><div id="local-search-results"></div></div></div><div id="search-mask"></div></div><div id="rightMenu"><div class="rightMenu-group rightMenu-small"><div class="rightMenu-item" id="menu-backward"><i class="anzhiyufont anzhiyu-icon-arrow-left"></i></div><div class="rightMenu-item" id="menu-forward"><i class="anzhiyufont anzhiyu-icon-arrow-right"></i></div><div class="rightMenu-item" id="menu-refresh"><i class="anzhiyufont anzhiyu-icon-arrow-rotate-right" style="font-size:1rem"></i></div><div class="rightMenu-item" id="menu-top"><i class="anzhiyufont anzhiyu-icon-arrow-up"></i></div></div><div class="rightMenu-group rightMenu-line rightMenuPlugin"><div class="rightMenu-item" id="menu-copytext"><i class="anzhiyufont anzhiyu-icon-copy"></i><span>复制选中文本</span></div><div class="rightMenu-item" id="menu-pastetext"><i class="anzhiyufont anzhiyu-icon-paste"></i><span>粘贴文本</span></div><a class="rightMenu-item" id="menu-commenttext"><i class="anzhiyufont anzhiyu-icon-comment-medical"></i><span>引用到评论</span></a><div class="rightMenu-item" id="menu-newwindow"><i class="anzhiyufont anzhiyu-icon-window-restore"></i><span>新窗口打开</span></div><div class="rightMenu-item" id="menu-copylink"><i class="anzhiyufont anzhiyu-icon-link"></i><span>复制链接地址</span></div><div class="rightMenu-item" id="menu-copyimg"><i class="anzhiyufont anzhiyu-icon-images"></i><span>复制此图片</span></div><div class="rightMenu-item" id="menu-downloadimg"><i class="anzhiyufont anzhiyu-icon-download"></i><span>下载此图片</span></div><div class="rightMenu-item" id="menu-newwindowimg"><i class="anzhiyufont anzhiyu-icon-window-restore"></i><span>新窗口打开图片</span></div><div class="rightMenu-item" id="menu-search"><i class="anzhiyufont anzhiyu-icon-magnifying-glass"></i><span>站内搜索</span></div><div class="rightMenu-item" id="menu-searchBaidu"><i class="anzhiyufont anzhiyu-icon-magnifying-glass"></i><span>百度搜索</span></div><div class="rightMenu-item" id="menu-music-toggle"><i class="anzhiyufont anzhiyu-icon-play"></i><span>播放音乐</span></div><div class="rightMenu-item" id="menu-music-back"><i class="anzhiyufont anzhiyu-icon-backward"></i><span>切换到上一首</span></div><div class="rightMenu-item" id="menu-music-forward"><i class="anzhiyufont anzhiyu-icon-forward"></i><span>切换到下一首</span></div><div class="rightMenu-item" id="menu-music-playlist" onclick="window.open(&quot;https://y.qq.com/n/ryqq/playlist/8802438608&quot;, &quot;_blank&quot;);" style="display:none"><i class="anzhiyufont anzhiyu-icon-radio"></i><span>查看所有歌曲</span></div><div class="rightMenu-item" id="menu-music-copyMusicName"><i class="anzhiyufont anzhiyu-icon-copy"></i><span>复制歌名</span></div></div><div class="rightMenu-group rightMenu-line rightMenuOther"><a class="rightMenu-item menu-link" id="menu-randomPost"><i class="anzhiyufont anzhiyu-icon-shuffle"></i><span>随便逛逛</span></a><a class="rightMenu-item menu-link" href="/categories/"><i class="anzhiyufont anzhiyu-icon-cube"></i><span>博客分类</span></a><a class="rightMenu-item menu-link" href="/tags/"><i class="anzhiyufont anzhiyu-icon-tags"></i><span>文章标签</span></a></div><div class="rightMenu-group rightMenu-line rightMenuOther"><a class="rightMenu-item" id="menu-copy" href="javascript:void(0);"><i class="anzhiyufont anzhiyu-icon-copy"></i><span>复制地址</span></a><a class="rightMenu-item" id="menu-commentBarrage" href="javascript:void(0);"><i class="anzhiyufont anzhiyu-icon-message"></i><span class="menu-commentBarrage-text">关闭热评</span></a><a class="rightMenu-item" id="menu-darkmode" href="javascript:void(0);"><i class="anzhiyufont anzhiyu-icon-circle-half-stroke"></i><span class="menu-darkmode-text">深色模式</span></a><a class="rightMenu-item" id="menu-translate" href="javascript:void(0);"><i class="anzhiyufont anzhiyu-icon-language"></i><span>轉為繁體</span></a></div></div><div id="rightmenu-mask"></div><div><script src="/js/utils.js"></script><script src="/js/main.js"></script><script src="/js/tw_cn.js"></script><script src="https://cdn.cbd.int/@fancyapps/ui@5.0.28/dist/fancybox/fancybox.umd.js"></script><script src="https://cdn.cbd.int/instant.page@5.2.0/instantpage.js" type="module"></script><script src="https://cdn.cbd.int/node-snackbar@0.1.16/dist/snackbar.min.js"></script><canvas id="universe"></canvas><script async src="https://npm.elemecdn.com/anzhiyu-theme-static@1.0.0/dark/dark.js"></script><script>var HoldLog=console.log;console.log=function(){};let now1=new Date;queueMicrotask(()=>{function o(){HoldLog.apply(console,arguments)}var c=new Date("04/11/2022 14:03:44"),c=(now1.setTime(now1.getTime()+250),(now1-c)/1e3/60/60/24),c=["欢迎使用安知鱼!","生活明朗, 万物可爱",`
        
       █████╗ ███╗   ██╗███████╗██╗  ██╗██╗██╗   ██╗██╗   ██╗
      ██╔══██╗████╗  ██║╚══███╔╝██║  ██║██║╚██╗ ██╔╝██║   ██║
      ███████║██╔██╗ ██║  ███╔╝ ███████║██║ ╚████╔╝ ██║   ██║
      ██╔══██║██║╚██╗██║ ███╔╝  ██╔══██║██║  ╚██╔╝  ██║   ██║
      ██║  ██║██║ ╚████║███████╗██║  ██║██║   ██║   ╚██████╔╝
      ╚═╝  ╚═╝╚═╝  ╚═══╝╚══════╝╚═╝  ╚═╝╚═╝   ╚═╝    ╚═════╝
        
        `,"已上线",Math.floor(c),"天","©2020 By 安知鱼 V1.6.12"],e=["NCC2-036","调用前置摄像头拍照成功，识别为【小笨蛋】.","Photo captured: ","🤪"];setTimeout(o.bind(console,`
%c${c[0]} %c ${c[1]} %c ${c[2]} %c${c[3]}%c ${c[4]}%c ${c[5]}

%c ${c[6]}
`,"color:#425AEF","","color:#425AEF","color:#425AEF","","color:#425AEF","")),setTimeout(o.bind(console,`%c ${e[0]} %c ${e[1]} %c 
${e[2]} %c
${e[3]}
`,"color:white; background-color:#4fd953","","",'background:url("https://npm.elemecdn.com/anzhiyu-blog@1.1.6/img/post/common/tinggge.gif") no-repeat;font-size:450%')),setTimeout(o.bind(console,"%c WELCOME %c 你好，小笨蛋.","color:white; background-color:#4f90d9","")),setTimeout(console.warn.bind(console,"%c ⚡ Powered by 安知鱼 %c 你正在访问 InsectMk 的博客.","color:white; background-color:#f0ad4e","")),setTimeout(o.bind(console,"%c W23-12 %c 你已打开控制台.","color:white; background-color:#4f90d9","")),setTimeout(console.warn.bind(console,"%c S013-782 %c 你现在正处于监控中.","color:white; background-color:#d9534f",""))})</script><script async src="/anzhiyu/random.js"></script><script async>!function(){var n,r,o,a,i,e=new Date("04/11/2022 14:03:44"),l=new Date;setInterval(()=>{var t;if(l=new Date,i=l.getHours(),t=(l-e)/1e3/60/60/24,n=Math.floor(t),t=(l-e)/1e3/60/60-24*n,r=Math.floor(t),1==String(r).length&&(r="0"+r),t=(l-e)/1e3/60-1440*n-60*r,o=Math.floor(t),1==String(o).length&&(o="0"+o),t=(l-e)/1e3-86400*n-3600*r-60*o,a=Math.round(t),1==String(a).length&&(a="0"+a),document.getElementById("footer")){let e="";e=(i<18&&9<=i||null!=(t=document.querySelector("#workboard .workSituationImg"))&&(t.src="",t.title="",t.alt=""),`本站居然运行了 ${n} 天<span id='runtime'> ${r} 小时 ${o} 分 ${a} 秒 </span><i class='anzhiyufont anzhiyu-icon-heartbeat' style='color:red'></i>`),document.getElementById("runtimeTextTip")&&(document.getElementById("runtimeTextTip").innerHTML=e)}},1e3)}()</script><script src="/js/search/local-search.js"></script><div class="js-pjax"><script>(()=>{let e=()=>{Waline.init(Object.assign({el:"#waline-wrap",serverURL:"https://waline-server.insectmk.cn/",pageview:!0,dark:'html[data-theme="dark"]',path:window.location.pathname,comment:!0},{reaction:["/static/img/waline/tieba_agree.png","/static/img/waline/tieba_look_down.png","/static/img/waline/tieba_sunglasses.png","/static/img/waline/tieba_pick_nose.png","/static/img/waline/tieba_awkward.png","/static/img/waline/tieba_sleep.png"],requiredMeta:["nick","mail"],locale:{placeholder:"欢迎评论哟~"}}))};var i=async()=>{"object"==typeof Waline||(await getCSS("https://cdn.cbd.int/@waline/client@2.15.5/dist/waline.css"),await getScript("https://cdn.cbd.int/@waline/client@2.15.5/dist/waline.js")),e()};setTimeout(i,0)})()</script><input type="hidden" name="page-type" id="page-type" value="post"></div><script>window.addEventListener("load",()=>{let t=e=>e=""!==e&&150<(e=(e=(e=(e=e.replace(/<img.*?src="(.*?)"?[^\>]+>/gi,"[图片]")).replace(/<a[^>]+?href=["']?([^"']+)["']?[^>]*>([^<]+)<\/a>/gi,"[链接]")).replace(/<pre><code>.*?<\/pre>/gi,"[代码]")).replace(/<[^>]+>/g,"")).length?e.substring(0,150)+"...":e,a=t=>{let a="";if(t.length)for(let e=0;e<t.length;e++)a=(a=(a+="<div class='aside-list-item'>")+`<a href='${t[e].url}' class='thumbnail'><img src='${t[e].avatar}' alt='${t[e].nick}'></a>`)+`<div class='content'>
        <a class='comment' href='${t[e].url}' title='${t[e].content}'>${t[e].content}</a>
        <div class='name'><span>${t[e].nick} / </span><time datetime="${t[e].date}">${anzhiyu.diffDate(t[e].date,!0)}</time></div>
        </div></div>`;else a+="没有评论";var e=document.querySelector("#card-newest-comments .aside-list");e&&(e.innerHTML=a),window.lazyLoadInstance&&window.lazyLoadInstance.update(),window.pjax&&window.pjax.refresh(e)};var e=()=>{var e;document.querySelector("#card-newest-comments .aside-list")&&((e=saveToLocal.get("waline-newest-comments"))?a(JSON.parse(e)):(async()=>{try{var e=(await(await fetch("https://waline-server.insectmk.cn/api/comment?type=recent&count=6",{method:"GET"})).json()).data.map(e=>({content:t(e.comment),avatar:e.avatar,nick:e.nick,url:e.url+"#"+e.objectId,date:e.time||e.insertedAt}));saveToLocal.set("waline-newest-comments",JSON.stringify(e),10/1440),a(e)}catch(e){console.error(e),document.querySelector("#card-newest-comments .aside-list").textContent="无法获取评论，请确认相关配置是否正确"}})())};e(),document.addEventListener("pjax:complete",e)})</script><script>var visitorMail=""</script><script async data-pjax src="https://cdn.cbd.int/anzhiyu-theme-static@1.0.0/waterfall/waterfall.js"></script><script src="https://lf3-cdn-tos.bytecdntp.com/cdn/expire-1-M/qrcodejs/1.0.0/qrcode.min.js"></script><link rel="stylesheet" href="https://cdn.cbd.int/anzhiyu-theme-static@1.1.9/icon/ali_iconfont_css.css"><script async src="//at.alicdn.com/t/c/font_3795172_6hp27xdg2x7.js"></script><script>(()=>{var a,t,h,e;window.ChatraSetup={startHidden:!0},window.chatBtnFn=()=>{document.getElementById("chatra").classList.contains("chatra--expanded")?(Chatra("minimizeWidget"),Chatra("hide")):(Chatra("openChat",!0),Chatra("show"))};a=document,t=window,h="Chatra",t.ChatraID="SjkKhfiLMpdfaPPhc",e=a.createElement("script"),t[h]=t[h]||function(){(t[h].q=t[h].q||[]).push(arguments)},e.async=!0,e.src="https://call.chatra.io/chatra.js",a.head&&a.head.appendChild(e)})()</script><link rel="stylesheet" href="https://cdn.cbd.int/anzhiyu-theme-static@1.0.0/aplayer/APlayer.min.css" media="print" onload='this.media="all"'><script src="https://cdn.cbd.int/anzhiyu-blog-static@1.0.1/js/APlayer.min.js"></script><script src="https://cdn.cbd.int/hexo-anzhiyu-music@1.0.1/assets/js/Meting2.min.js"></script><script src="https://cdn.cbd.int/pjax@0.2.8/pjax.min.js"></script><script>let pjaxSelectors=["head > title","#config-diff","#body-wrap","#rightside-config-hide","#rightside-config-show",".js-pjax"];var pjax=new Pjax({elements:'a:not([target="_blank"])',selectors:pjaxSelectors,cacheBust:!1,analytics:!1,scrollRestoration:!1});document.addEventListener("pjax:send",function(){if(anzhiyu.removeGlobalFnEvent("pjax"),anzhiyu.removeGlobalFnEvent("themeChange"),document.getElementById("rightside").classList.remove("rightside-show"),window.aplayers)for(let e=0;e<window.aplayers.length;e++)window.aplayers[e].options.fixed||window.aplayers[e].destroy();"object"==typeof typed&&typed.destroy();var e=document.body.classList;e.contains("read-mode")&&e.remove("read-mode")}),document.addEventListener("pjax:complete",function(){window.refreshFn(),document.querySelectorAll("script[data-pjax]").forEach(e=>{let t=document.createElement("script");var a=e.text||e.textContent||e.innerHTML||"";Array.from(e.attributes).forEach(e=>t.setAttribute(e.name,e.value)),t.appendChild(document.createTextNode(a)),e.parentNode.replaceChild(t,e)}),GLOBAL_CONFIG.islazyload&&window.lazyLoadInstance.update(),"function"==typeof panguInit&&panguInit(),"function"==typeof gtag&&gtag("config","",{page_path:window.location.pathname}),"object"==typeof _hmt&&_hmt.push(["_trackPageview",window.location.pathname]),"function"==typeof loadMeting&&document.getElementsByClassName("aplayer").length&&loadMeting(),"object"==typeof Prism&&Prism.highlightAll()}),document.addEventListener("pjax:error",e=>{404===e.request.status&&pjax.loadUrl("/404")})</script><script async data-pjax src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script><script charset="UTF-8" src="https://cdn.cbd.int/anzhiyu-theme-static@1.1.5/accesskey/accesskey.js"></script></div><div id="popup-window"><div class="popup-window-title">通知</div><div class="popup-window-divider"></div><div class="popup-window-content"><div class="popup-tip">你好呀</div><div class="popup-link"><i class="anzhiyufont anzhiyu-icon-arrow-circle-right"></i></div></div></div></body></html>